Kostya F. 正在穿越某个国家的边境，随身携带了 $n$ 件应税物品。每件物品由两个整数 $w_i$ 和 $c_i$ 刻画：$w_i$ 为物品的重量，$c_i$ 为携带该物品过境所需缴纳的税额。

Kostya 需要将所有物品分配到若干个背包中。他可以使用任意数量的背包。根据航空公司的规定，每个背包的重量有限，因此每个背包内物品的总重量不能超过 $W$。

海关费用有特殊的规定。当海关人员检查行李时，他们会打开每个背包，并将该背包的税额设定为该背包内所有物品税额的最大值。总税额为所有背包税额之和。

出于实际考虑，Kostya 想知道他为了携带所有物品过境所能支付的最小总税额是多少。此外，出于好奇，他还想知道有多少种不同的方式可以达到这个最小值。请帮助他。由于方案数可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

如果两个物品分配方案之间存在一种背包的双射，使得对应的背包中包含的物品集合完全相同，则认为这两个方案是相同的。

输入格式

第一行包含两个整数：物品数量 $n$ 和单个背包的最大重量 $W$ ($1 \le n \le 22; 1 \le W \le 5 \cdot 10^7$)。

接下来的 $n$ 行描述物品。第 $i$ 行包含两个整数：物品 $i$ 的重量 $w_i$ 和税额 $c_i$ ($1 \le w_i \le W; 1 \le c_i \le 5 \cdot 10^7$)。

输出格式

输出一行，包含两个整数。第一个整数是 Kostya 所能支付的最小总税额。第二个整数是达到该最小值的方案数，对 $998\,244\,353$ 取模。

样例

样例输入 1

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

样例输出 1

9 4

说明

在样例中，有 4 种不同的方式将物品分配到背包中，使得总税额等于 9（物品编号为 1 到 5）：

• $[1, 3], [2, 4, 5]$：税额 $5 + 4 = 9$
• $[1, 4], [2, 3, 5]$：税额 $5 + 4 = 9$
• $[1, 5], [2, 3, 4]$：税额 $5 + 4 = 9$
• $[1, 2], [3, 4], [5]$：税额 $5 + 3 + 1 = 9$