最终检验（verify）

题目描述

一座历史档案馆正在修复一批年代久远的文献。

由于档案馆使用的是早期的机械设备，所有文献都必须经过密码盘解锁，才能进行影印。

馆内共有 (n) 份待修复的文献。每份文献都附有一块金属铭牌和一份页数记录。

档案管理员需要在设备使用次数有限的情况下，尽可能完整地制作一册影印汇编。

不过，这台设备的操作方式十分特殊。

密码盘

影印设备安装了若干个数字转盘，每个转盘上依次刻有数字：

0、1、2、3、4、5、6、7、8、9

每个转盘只能沿数字减小的方向转动。转盘每转过一个相邻刻度，设备就会记录一次机械动作。

当某个转盘显示 0 时，它便无法继续转动。

使用一份文献前，管理员必须将铭牌上的十进制编号完整显示在密码盘上，每个数字占据一个独立的转盘。

随后，管理员必须将所有转盘调整到 0，设备才允许开始影印。

例如，铭牌上刻有 407，那么管理员需要分别将显示 4、0、7 的三个转盘调整至 0。

设备不会自动完成这一过程。

每开始新一轮影印，都需要重新输入铭牌编号并完成上述操作。

文献使用许可

档案馆对不同文献实行两种许可制度。

许可的类型与铭牌上的完整编号有关。

对于编号为 (x) 的文献，档案管理员会使用一台旧式齿轮检测器。

检测器上有一个由 (x) 个刻度组成的圆环。

管理员可以为检测器设置一个正整数步长 (d)，但必须满足 $(1\le d\le x)$。

检测器从起始刻度出发，每次沿圆环前进 (d) 个刻度。

如果检测器能够在前进若干次后第一次返回起点时，恰好累计前进 (x) 个刻度，那么称 (d) 是一个合格步长。

档案管理员会统计该编号对应的不同合格步长的数量。

按照馆内规定：

• 如果恰好存在 2 个不同的合格步长，这份文献可以多次申请影印，每次申请都需要重新解锁设备。
• 否则，这份文献只能申请影印一次。

每份文献的使用许可单独管理。

汇编装订

每份文献对应的页数记录为 $(v_i)$。

当某份文献完成一次影印后，工作人员会把这份文献的全部 $(v_i)$页影印稿依次装订到汇编末尾。

不同文献可以按任意顺序影印，也可以根据许可规定重复影印同一份文献。

但汇编一旦装入页面，就不能再删除其中的任何一页。

档案馆使用一台机械装订计数器。

计数器只有两个显示状态：A 和 B。

开始装订前，计数器显示 A。

之后，每装入一页影印稿，计数器就会改变一次状态：

• A 切换为 B；
• B 切换为 A。

所有影印与装订工作结束后，管理员必须进行最终检验。

只有计数器停留在 B 状态，整册汇编才会被档案馆接收。

修复任务

本次修复工作中，影印设备最多允许记录 (V) 次机械动作。

管理员可以自由选择文献及其影印顺序，但必须遵守每份文献的使用许可。

如果某次解锁需要的机械动作次数超过设备剩余的可用次数，那么这次影印无法进行。

档案馆希望在汇编能够通过最终检验的前提下，使装订完成的页面总数尽可能多。

请计算，最终能够被档案馆接收的汇编最多包含多少页。

如果无法制作出任何能够通过检验的汇编，输出 -1。

输入格式

第一行包含两个整数 (n,V)，分别表示待修复文献的数量和影印设备允许记录的机械动作总次数。

接下来 (n) 行，每行包含两个整数 $(a_i,v_i)$，分别表示第 (i) 份文献的铭牌编号及其页数记录。

输出格式

输出一个整数，表示能够通过最终检验的汇编所包含的最多页数。

如果不存在合法方案，输出 -1。

输入输出样例 #1

输入

4 11
12 5
13 7
22 9
17 12

输出

21

样例解释

管理员可以分别影印编号为 12、13 和 22 的文献一次。

这三次解锁分别需要记录 3、4、4 次机械动作，共计 11 次，没有超出设备限制。

三份文献共包含 21 页。

由于装订开始时计数器显示 A，完成 21 页的装订后，计数器最终显示 B。

因此，该汇编能够通过最终检验。

可以证明，不存在页数更多且满足全部规定的方案。

数据范围

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

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

说明

• 不同文献的使用许可分别管理，即使铭牌编号相同，也视为不同文献。
• 每轮影印都需要重新完成密码盘解锁。
• 解锁过程中转盘显示为 0 时，无需进行机械动作。
• 影印必须完整进行，不允许只装订某份文献的部分页面。
• 不要求将全部机械动作次数用完。
• 不进行任何影印时，计数器保持 A 状态，不能通过最终检验。

测试点编号	层级	n	V	数据特征	标准输出	设计目的
1	弱数据	3	10	所有物品价值均为偶数	-1	检查不存在奇数总价值方案
2		1		质数编号 2，奇数价值 3	15	检查质数编号可重复选择及奇偶变化
3	基础数据		4	最多能选两件，但两件价值和为偶数	3	检查容量不必用满，只选一件得到奇数价值
4			10	非质数编号 4，物品只能选择一次	7	检查完整编号的质数判定与 0/1 限制
5	正常数据	4		质数、非质数编号及奇偶价值混合	27	综合检查可选次数和价值奇偶状态
6		3	8	普通最大价值为偶数 40	35	检查必须舍弃偶数最优、选择奇数方案
7	较强数据	5	12	多个奇偶价值和不同数位和重量		检查多步奇偶状态转换
8	正常数据	3	9	12、21 非质数，3 为质数，重量均为 3	29	检查判断完整编号而非数位和
9	极限价值	2	2000	一个偶数价值和一个奇数价值的完全背包物品	1997999999999	检查奇数件约束及 long long 大数
10	极限规模	100		编号为 1～100，价值为编号平方	1280657	检查最大规模、数位和、连续判质和奇偶 DP