Story

After a while, yuusaan came back carrying a knapsack.

"I'm surprised. It seems that things with negative mass exist in this world. There are also plenty of other things worth studying. Honestly, I'd like to take everything home... but it would all be for nothing if the knapsack broke, so I'll hold back to just short of the point where it breaks.

All right, I'll assign an importance to each candidate item to take home, so please make it possible to calculate what the total importance comes to when it is made as large as possible while everything still fits in the knapsack.

And if there are several ways of choosing that give the maximum total importance, I'd like you to tell me that as well."

Problem Statement

yuusaan has a knapsack with durability $W$.

yuusaan wants to put various items into this knapsack so that the total value of the items put in is maximized.

There are $N$ candidate items to put in the knapsack, numbered in order as item $1$ , item $2$ , and so on.

Some items may have negative weight or negative value, but it is guaranteed that there is no way of choosing items such that the total weight is less than $-10000$.

Here, item $i$ has value $v_i$ and weight $w_i$.

Suppose that $0$ or more items are put in the knapsack so that the total weight is at most $W$. Find the maximum possible total value and the number of ways of putting in items that achieve the maximum total value.

Here, it is guaranteed that there always exists a way of putting in items such that the total weight is at most $W$.

Since the number of ways can be very large, output it modulo $998244353$.

Two ways of putting in items are considered different if there exists an item that is put in under one way and not put in under the other.

Input

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

Constraints

• $1\leq N \leq 100$
• $|W|$ $\leq 10000$
• $|w_i|$ $\leq 10000$
• $|v_i|$ $\leq 10^6$
• There is no way of choosing items such that the total weight is less than $-10000$
• There always exists a way of putting in items such that the total weight is at most $W$
• All inputs are integers

Output

Output the maximum possible total value and the number of ways of putting in items that achieve the maximum total value, in this order, separated by a space, on one line.

Note that the number of ways of putting in items that achieve the maximum total value must be output modulo $998244353$.

Sample

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