ストーリー

ゆ～さんはしばらくしてナップサックを持って戻ってきました。

「驚いた。この世界には負の質量を持つものが存在するようだ。それ以外にも研究しがいのあるものがたくさんある。正直全部持ち帰りたいが...ナップサックが壊れたら元も子もないから壊れないギリギリで我慢しよう。

よし、持ち帰るものの候補にそれぞれ重要度を決めておくから、ナップサックに入りきるように重要度の合計をなるべく大きくしたときいくつになるか計算できるようにしておいてくれ。

そのとき、もし重要度の合計が最大となる選び方がいくつかあったら、その旨も教えて欲しい。」

問題文

ゆ～さんは耐久値 $W$ のナップッサックをもっています。

ゆ～さんはこのナップサックにいろいろな荷物を入れて入れた荷物の合計価値が最大になるようにしたいです。

ナップサックに入れる荷物の候補は $N$ 個存在し、順に荷物 $1$ ,荷物 $2$ ,...と番号がついています。

荷物には負の重さや負の価値を持つものが存在する可能性がありますが、重さの合計が $-10000$ 未満となる荷物の選び方は存在しないことが保証されます。

ここで、荷物 $i$ の価値は $v_i$ 、重さは $w_i$ です。

ナップサックには 重さの合計が $W$ 以下になるように $0$ 個以上の荷物を入れるとしたとき、あり得る最大の合計価値および合計価値が最大となる荷物の入れ方の個数を求めてください。

ここで、重さの合計が $W$ 以下になる荷物の入れ方は必ず存在することが保証されます。

ただし、求める荷物の入れ方の個数はとても大きくなる可能性があるため、 $998244353$ で割ったあまりを出力してください。

なお、二つの荷物の入れ方は、片方の入れ方では入っていてもう片方の入れ方では入っていない荷物が存在するとき、区別します。

入力

$N\ W$
$v_1\ w_1$
$v_2\ w_2$
$\vdots$
$v_N \ w_N$

制約

• $1\leq N \leq 100$
• $|W|$ $\leq 10000$
• $|w_i|$ $\leq 10000$
• $|v_i|$ $\leq 10^6$
• 重さの合計が $-10000$ 未満になる物の選び方は存在しない
• 重さの合計が $W$ 以下になる荷物の入れ方は必ず存在する
• 入力は全て整数

出力

あり得る最大の合計価値と価値の合計が最大となる物の入れ方の個数をこの順で空白区切りで一行に出力して下さい。

ただし、価値の合計が最大となる物の入れ方の個数は $998244353$ で割ったあまりを出力する点に注意してください。

サンプル

5 10
4 3
2 1
5 5
4 4
3 3

11 3

2 0
-100 -100
500 100

400 1

6 -2
6 5
1 -6
6 4
6 6
-3 -5
7 -2

17 3