Crossing the Border

Kostya F. is crossing the border of a certain country with $n$ taxable items. Each item $i$ is described by two integers $w_i$ (its weight) and $c_i$ (the tax paid to carry it across the border).

Kostya must distribute all items among knapsacks. He may use any number of knapsacks. The total weight of the items in each knapsack cannot exceed $W$.

Customs uses a special rule. The officers open each knapsack and set its tax to the maximum $c_i$ among the items inside it. The total tax is the sum of the taxes of all knapsacks.

Find the minimum total tax Kostya can pay, and the number of ways to achieve it. Since the count can be very large, output it modulo $998\,244\,353$. Two distributions are the same if there is a bijection between knapsacks such that matching knapsacks hold exactly the same sets of items.

The first line contains two integers $n$ and $W$ ($1 \le n \le 22$; $1 \le W \le 5 \cdot 10^7$).

Each of the next $n$ lines contains two integers $w_i$ and $c_i$ ($1 \le w_i \le W$; $1 \le c_i \le 5 \cdot 10^7$).

Print two integers: the minimum total tax, and the number of ways to achieve it modulo $998\,244\,353$.

In the example, items are numbered from 1 to 5. There are 4 ways to reach the total tax of 9:

• [1, 3], [2, 4, 5]: tax 5 + 4 = 9
• [1, 4], [2, 3, 5]: tax 5 + 4 = 9
• [1, 5], [2, 3, 4]: tax 5 + 4 = 9
• [1, 2], [3, 4], [5]: tax 5 + 3 + 1 = 9