题目描述

为了给自己选举大队长造势，断罪小学三年6班的李子明同学决定给他身边的同学发放旺仔牛奶，在同学之间拉拢人气。
根据自己在大队内部的工作经验，李子明对三年级的每名同学做了一系列分析：他的潜在目标共有\(N\)人，如果给第\(i\)名学生赠送不少于\(t_i\)罐旺仔牛奶，那么该名同学就会为他拉拢\(c_i\)点人气，\(i=1,2 \cdots N\)。但李子明不想过早让他的父母知道自己贿选的事，所以他只能用自己的零花钱充当经费。由于经费有限，李子明只买得起\(T\)罐旺仔牛奶，而他也很可能得放弃一些潜在目标。为了让拉票的效率尽可能高，所以他打算用剩下的一点经费请你帮他编写一个程序，为他设计一个拉拢尽可能多人气值的方案。
不巧的是，在他买旺仔牛奶的时候，他自言自语的话被另一个大队长候选人偷偷录了下来，所以李子明不得不把原本用来买旺仔牛奶的钱用在了危机公关上，请人写程序的钱就更不存在了。请你计算一下，如果“录音门” 没有发生，那么李子明最多可以用这\(T\)罐旺仔牛奶拉拢到多少人气值？有多少种方案使得他拉拢到的人气值最高？
这里“不同方案”的严格定义是：对于两种方案，若存在某个人，他在且只在其中一种方案里边，那么就说这两种方案是不同的。

I/O格式

输入

第一行是两个正整数\(N, T\)；
之后\(N\)行分别描述\(N\)名同学的信息，每行两个正整数\(t_i, c_i\)，含义见上。

输出

在一行内输出两个正整数\(C_{max}, K\)，分别表示最大人气值，以及得到最大人气值的方案。输出时两个整数用一个空格隔开。

样例

输入

3 5
2 6
3 7
4 13

输出

13 2

数据规模及约定

\(N \le 300, \quad T \le 3 \times 10^4, \quad t_i \le T, \quad c_i \le 10^6, \quad K \le 10^6\)
70%的数据满足：\(K = 1\)
时间限制1s，空间限制256MB。