#P18479. Crossing the Border
Crossing the Border
Crossing the Border
Kostya F. 正带着 件需要缴税的物品穿越某个国家的边境。每件物品由两个整数 描述,分别表示它的重量,以及把它带过边境需要缴纳的税额。
Kostya 要把所有物品分配到若干个背包中,背包的数量不限。根据航空公司的规定,每个背包中物品的总重量不能超过 。
海关有一项特殊的征税规定:检查行李时,海关人员会打开每个背包,把该背包的税额定为其中所有物品税额的最大值。总税额等于各个背包税额的总和。
出于实际需要,Kostya 想知道他带着全部物品过境时,最少需要缴纳多少税。此外,他还想知道有多少种不同的分配方法能达到这个最小总税额。方案数可能很大,只需输出它对 取模的结果。
如果两种分配方法的背包之间存在一个双射,使每对相对应的背包包含完全相同的物品集合,则把这两种方法视为相同。也就是说,背包没有编号,而每件物品仍由其输入位置区分;即使两件物品重量和税额相同,它们也是不同物品。使用的每个背包至少放一件物品。
输入格式
第一行包含两个整数 ,分别表示物品数量和一个背包允许的最大总重量:
接下来 行,第 行包含两个整数 ,表示第 件物品的重量和税额:
输出格式
输出一行,两个整数:最小总税额,以及达到该总税额的分配方案数对 取模的结果。
原样例
5 5
3 5
1 4
2 3
2 2
2 1
9 4
样例说明
样例中有以下 4 种不同的分配方法,总税额都是 9。物品按照输入顺序编号为 1 至 5:
- 、:税额为 。
- 、:税额为 。
- 、:税额为 。
- 、、:税额为 。