33372번 - Crossing the Border 다국어

문제

Kostya F. is crossing the border of a certain country, carrying $n$ taxable items with him. Each item is characterized by two integers $w_i$ and $c_i$: the weight of the item and the amount of tax that must be paid for transporting this item across the border.

Kostya needs to distribute all his items among several knapsacks. He can use any number of knapsacks. According to the airline's rules, the weight of each knapsack is limited, so the total weight of items inside each knapsack cannot exceed $W$.

There are special rules for customs fees. When customs officers are checking the luggage, they open each knapsack, and set the tax for it equal to the maximum tax rate among the items inside this knapsack. The total tax is the sum of individual taxes for all knapsacks.

For purely practical reasons, Kostya wants to know what is the minimum total tax he can pay in order to cross the border with all his items. Also, out of pure curiosity, he wants to know in how many different ways this minimum can be achieved. Help him. Since the number of ways can be very large, you should find it modulo 998ドル,244円,353円$.

Two ways to put items into knapsacks are considered the same if there is a bijection between knapsacks such that the corresponding knapsacks have exactly the same sets of items.

입력

The first line contains two integers: the number of items $n$ and the maximum weight of one knapsack $W$ (1ドル \le n \le 22$; 1ドル \le W \le 5 \cdot 10^7$).

The next $n$ lines describe the items. The $i$-th of them contains two integers: the weight $w_i$ and tax $c_i$ for item $i$ (1ドル \le w_i \le W$; 1ドル \le c_i \le 5 \cdot 10^7$).

출력

Print a line with two integers. The first must be the minimum total tax Kostya can pay. The second must be the number of ways to achieve that minimum, taken modulo 998ドル,244円,353円$.

제한

노트

In the example, there are 4ドル$ different ways to distribute items among knapsacks with total tax equal to 9ドル$ (items are numbered from 1ドル$ to 5ドル$):

• $[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$