特殊物资（special）

题目描述

某实验基地正在进行一项长期研究。

基地中保存着 (n) 种特殊物资，每种物资都有一个独立的数字档案。

为了确保实验数据可靠，基地要求所有物资在使用前都必须经过一套特殊的身份核验程序。

第 (i) 种物资的档案编号为 $(a_i)$。每成功完成一次该种物资的实验，就可以向研究数据库提交 $(v_i)$条有效记录。

但是，物资的使用权限和实验次数并不是固定的。

身份核验

每次开展实验前，工作人员需要将物资编号输入核验设备。

设备会从编号的最右侧开始，逐位读取，直到所有数字都被读取完毕。

每读取到一个数字 (d)，设备就必须执行 (d) 次校验操作。

例如，对于编号 314：

• 读取数字 4，执行 4 次校验操作。
• 读取数字 1，执行 1 次校验操作。
• 读取数字 3，执行 3 次校验操作。

完成整个核验过程共执行 8 次校验操作。

如果编号中出现数字 0，设备仍然会读取该数字，但不需要执行校验操作。

每次开展实验，都必须重新执行完整的身份核验。

实验授权

除了身份核验，基地还需要为不同物资确定实验授权方式。

对于某种物资，设完成一次身份核验需要执行 (x) 次校验操作。

审核人员会尝试将 (x) 个相同的校验标记分成若干组，要求：

• 每组至少包含一个标记。
• 同一方案中，每组包含的标记数量必须相同。
• 如果两种方案的分组数量不同，则视为不同的方案。

例如：

当 (x=6) 时，可以分为：

• 1 组，每组 6 个标记；
• 2 组，每组 3 个标记；
• 3 组，每组 2 个标记；
• 6 组，每组 1 个标记。

因此，共有 4 种不同的分组方案。

当 (x=5) 时，只能分为 1 组或 5 组，因此共有 2 种不同的分组方案。

审核完成后，基地根据结果发放授权：

• 如果某种物资恰好只有 2 种不同的分组方案，那么该种物资可以在完成核验后反复用于实验。
• 如果不满足上述条件，那么该种物资只允许进行一次实验，完成后便会被封存。

不同种类的物资分别进行授权管理。

研究任务

本次研究开始前，实验基地为核验设备预留了 (V) 次校验操作。

所有实验都必须通过身份核验才能开展。每次成功完成实验，才能向研究数据库提交对应数量的有效记录。

工作人员可以自由安排物资的使用顺序和实验次数，也可以选择不使用某些物资。

但是，整个研究过程中，核验设备实际执行的校验操作总次数不能超过 (V)。

研究负责人希望在现有条件下，尽可能多地收集有效实验记录。

请你计算，本次研究最多能够向数据库提交多少条有效记录。

输入格式

第一行包含两个正整数 (n,V)，分别表示特殊物资的种类数量，以及本次研究允许执行的校验操作总次数。

接下来 (n) 行，每行包含两个正整数 $(a_i,v_i)$，分别表示第 (i) 种物资的档案编号，以及每次成功完成该种物资实验后能够提交的有效记录数量。

输出格式

输出一个整数，表示本次研究最多能够提交的有效记录总数。

输入输出样例 #1

输入

4 10
10 9
12 5
14 9
22 8

输出

26

样例解释

根据核验与授权规则，各种物资的情况如下：

物资编号	单次核验操作次数	授权情况	单次实验记录数
10	1	只能实验一次	9
12	3	可以重复实验	5
14	5		9
22	4	只能实验一次	8

工作人员可以安排以下实验：

• 使用编号 10 的物资进行一次实验。
• 使用编号 14 的物资进行一次实验。
• 使用编号 22 的物资进行一次实验。

这三次实验需要执行的校验操作总数为：

$1+5+4=10$

获得的有效记录总数为：

$9+9+8=26$

不存在能够获得更多有效记录的合法方案。

因此输出 26。

数据范围

对于所有测试数据，保证：

• $(1\le n\le100)$
• $(1\le V\le2000)$
• $(1\le a_i\le10^9)$
• $(1\le v_i\le10000)$

说明

• 不同输入行代表不同种类的物资，即使编号相同，也分别进行授权管理。
• 每次实验都需要完整执行该物资对应的身份核验。
• 只有成功完成的实验才能获得有效记录。
• 校验操作次数可以少于 (V)，不要求恰好用完。
• 不进行任何实验也是合法方案，此时获得的有效记录数为 0。

测试点编号	层级	n	V	数据特征	标准输出	设计目的
1	弱数据	1	5	编号 1，数位和为非质数 1	7	检查非质数重量最多选择一次
2			10	编号 2，数位和为质数 2	15	检查质数重量可以重复选择
3	基础数据			编号 11，数位和为质数 2	20	检查判断对象是数位和而非编号
4				编号 13，数位和为合数 4	7	检查合数重量的 0/1 限制
5	正常数据	6	20	数位和覆盖 1、2、3、4、5、11	142	检查典型质数与合数分类
6		4	12	3 与 12 的数位和均为质数 3	33	检查相同质数重量的不同完全背包物品
7		3	10	数位和为 6、8、27，均非质数	22	检查容量剩余、0/1 限制和超重编号
8	较强数据	4		完全背包与 0/1 物品混合	55	卡按单项价值直接贪心
9	极限价值	1	2000	数位和 2、价值 2×10⁹	2000000000000	检查大量重复选择及 long long
10	极限规模	100		编号为 1～100，价值为数位和平方	33948	检查最大规模、连续数位和、判质及混合转移