#P18479. Crossing the Border

Crossing the Border

Crossing the Border

Kostya F. 正带着 nn 件需要缴税的物品穿越某个国家的边境。每件物品由两个整数 wi,ciw_i,c_i 描述,分别表示它的重量,以及把它带过边境需要缴纳的税额。

Kostya 要把所有物品分配到若干个背包中,背包的数量不限。根据航空公司的规定,每个背包中物品的总重量不能超过 WW。

海关有一项特殊的征税规定:检查行李时,海关人员会打开每个背包,把该背包的税额定为其中所有物品税额的最大值。总税额等于各个背包税额的总和。

出于实际需要,Kostya 想知道他带着全部物品过境时,最少需要缴纳多少税。此外,他还想知道有多少种不同的分配方法能达到这个最小总税额。方案数可能很大,只需输出它对 998 244 353998\,244\,353 取模的结果。

如果两种分配方法的背包之间存在一个双射,使每对相对应的背包包含完全相同的物品集合,则把这两种方法视为相同。也就是说,背包没有编号,而每件物品仍由其输入位置区分;即使两件物品重量和税额相同,它们也是不同物品。使用的每个背包至少放一件物品。

输入格式

第一行包含两个整数 n,Wn,W,分别表示物品数量和一个背包允许的最大总重量:

1≤n≤22,1≤W≤5⋅107.1\le n\le22,\qquad 1\le W\le5\cdot10^7.

接下来 nn 行,第 ii 行包含两个整数 wi,ciw_i,c_i,表示第 ii 件物品的重量和税额:

1≤wi≤W,1≤ci≤5⋅107.1\le w_i\le W,\qquad1\le c_i\le5\cdot10^7.

输出格式

输出一行,两个整数:最小总税额,以及达到该总税额的分配方案数对 998 244 353998\,244\,353 取模的结果。

原样例

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

样例说明

样例中有以下 4 种不同的分配方法,总税额都是 9。物品按照输入顺序编号为 1 至 5:

  • [1,3][1,3]、[2,4,5][2,4,5]:税额为 5+4=95+4=9。
  • [1,4][1,4]、[2,3,5][2,3,5]:税额为 5+4=95+4=9。
  • [1,5][1,5]、[2,3,4][2,3,4]:税额为 5+4=95+4=9。
  • [1,2][1,2]、[3,4][3,4]、[5][5]:税额为 5+3+1=95+3+1=9。