积分挑战（score）

题目描述

某科技中心正在举办一场特殊的积分挑战赛。

比赛设置了 (n) 种挑战项目，每种项目都有一个专属的正整数编号$(a_i)。参赛者每成功完成一次第 (i)$ 种挑战，就可以获得 $(v_i)$ 分。

与普通比赛不同，本次比赛的挑战项目需要通过一套特殊的验证系统才能开始。

挑战验证

每次开始挑战前，系统会从项目编号的最右侧开始，依次读取其中的每一位数字。

当系统读取到数字 (d) 时，需要执行 (d) 次验证操作。每执行一次操作，都会消耗 1 个操作额度。

例如，某项目的编号为 305，验证过程如下：

• 读取数字 5，执行 5 次操作；
• 读取数字 0，不执行操作；
• 读取数字 3，执行 3 次操作。

只有完整读取全部数字并完成相应操作，参赛者才能开始挑战。

挑战权限

竞赛系统还为每种挑战项目设置了一个权限标记。

每次验证开始时，权限标记都处于蓝色状态。

系统每读取完一位数字，权限标记就会切换一次颜色：

• 蓝色变为红色；
• 红色变为蓝色。

验证结束后，系统根据权限标记的最终颜色决定该项目的后续使用权限。

如果最终为红色，项目会继续保留，参赛者以后仍然可以再次挑战。

如果最终为蓝色，项目会被系统锁定，参赛者不能再挑战该项目。

每次重新验证时，权限标记都会恢复为蓝色。

比赛要求

本次比赛采用累计计分制。

同一种项目如果能够反复挑战，那么每次成功完成后，都可以再次获得对应分数。

参赛者可以自行决定挑战项目的顺序和次数，也可以放弃某些项目。

比赛开始时，每位参赛者拥有 (V) 个操作额度。比赛过程中无法补充，所有挑战消耗的操作额度总数不能超过 (V)。

现在，请你帮助一名参赛者制定挑战方案，使他在比赛结束时获得的累计总分尽可能高。

输入格式

第一行包含两个正整数 (n,V)，分别表示挑战项目的种类数量和参赛者拥有的操作额度。

接下来 (n) 行，每行包含两个正整数 (a_i,v_i)，分别表示第 (i) 种挑战项目的编号以及每次成功完成后获得的分数。

输出格式

输出一个整数，表示参赛者最多能够获得的累计总分。

输入输出样例 #1

输入

4 10
23 9
111 5
40 7
7 10

输出

17

样例解释

参赛者可以采用以下挑战方案：

首先完成编号为 111 的项目一次。

该项目需要消耗 3 个操作额度，完成后获得 5 分。验证结束时权限标记为红色，因此该项目仍然允许再次挑战。

接着，再次完成编号为 111 的项目，消耗 3 个操作额度，获得 5 分。

最后完成编号为 40 的项目，消耗 4 个操作额度，获得 7 分。

因此，总共消耗：

$3+3+4=10$

最终获得：

$5+5+7=17$ 分。

可以证明，不存在获得更高总分的合法挑战方案。

数据范围

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

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

说明

• 不同输入行代表不同的挑战项目，即使编号相同，也分别管理挑战权限。
• 所有项目编号均采用十进制表示，不包含前导零。
• 每次完成挑战都必须执行完整的验证过程。
• 若操作额度不足以完成某次验证，则该次挑战无法开始。
• 不进行任何挑战也是合法方案，此时最终得分为 0。

测试点编号	层级	n	V	数据特征	标准输出	设计目的
1	弱数据	1	5	一位数编号，重量为 1	10	检查奇数位编号可以重复选择
2			10	两位数编号，重量为 2	7	检查偶数位编号最多选择一次
3	基础数据	2	9	3 与 12 的数位和均为 3，位数奇偶不同	20	检查相同重量下的完全与 0/1 类型差异
4	正常数据	6	30	包含 9/10、99/100、999/1000	97	检查位数临界变化及含零数字的数位和
5		4	12	四个编号的数位和均为 3，位数分别为 1～4	44	综合检查同重量、不同库存类型
6		3	10	最优方案只使用 8 单位容量，含超重编号	22	检查容量不要求用满及超重处理
7	较强数据	4		完全背包与 0/1 物品混合	55	卡按单项价值或简单性价比贪心
8	边界数据	5		包含数位和 81、82、45 的超重编号	23	检查大整数数位和及含零编号
9	极限价值	1	2000	重量 1、价值 2×10⁹ 的一位数编号	4000000000000	检查大量重复选择与 long long
10	极限规模	100		50 个三位数和50个四位数，价值为数位和平方	27976	检查最大规模、连续数位计算和混合转移