問題文

$1$ ~ $N$ の番号が付いたお菓子が $1$ 個ずつ入ったお菓子セットがある。お菓子にはそれぞれに体積と美味しさが設定されている。

お菓子 $i$ の体積は $v_i$ で、美味しさは $a_i$ である。

あなたはお菓子セットを好きな数だけ用意して、セット内のお菓子を食べることができる。 ただし、食べたお菓子の体積の合計が $V$ 以下になるように食べなければならないとする。

食べたお菓子の美味しさの合計の最大値と、それを達成するために必要なお菓子セットの最小個数を出力するようなプログラムを作成せよ。

出力は 64 bit整数に収まることが保証されます。

制約

$1\leq N, V \leq 1000$

$1\leq v_i \leq V$ $(1\leq i \leq N)$

$1\leq a_i \leq 10^9$ $(1\leq i \leq N)$

入力

入力はすべて整数である。

N V
v_1 a_1
v_2 a_2
...
v_N a_N

出力

食べたお菓子の美味しさの合計の最大値と、それを達成するために必要なお菓子セットの最小個数をこの順に半角空白区切りで一行に出力せよ。

サンプル

3 10
1 2
3 1
4 9

22 2

お菓子セット $1$ 個では食べたお菓子の美味しさの総和は最大でも $12$ にしかなりません。

お菓子セット $2$ 個だと食べたお菓子の美味しさの総和は $22$ にでき、これが最大となります。

3 1000
7 665040040
2 382793173
9 598410644

191396586500 500

出力が 32 bit整数に収まらない場合もあります。