发运清单（cargo）

题目描述

一家物流公司正在整理一批即将发出的货物。

由于近期物流系统进行了升级，所有货物在正式发出之前，都必须完成一次编号核验。

仓库中共有 (n) 件货物，每件货物都具有一个唯一的正整数编号 $(a_i)$。完成第 (i) 件货物的核验后，公司可以获得 $(v_i)$ 点工作积分。

编号核验需要使用一种特殊的电子校验单元。

核验设备会从右向左，依次读取货物编号中的每一位数字。每读取一个数字 (d)，设备就会消耗 (d) 个电子校验单元。

例如，核验编号为 3052 的货物时，设备依次读取：

2 → 5 → 0 → 3

四次读取分别消耗 2、5、0、3 个电子校验单元。

只有完整核验一件货物的全部数字，才能获得对应的工作积分。未完成的核验不会获得积分，也不会退还已经消耗的校验单元。

目前，仓库只剩下 (V) 个电子校验单元，且短时间内无法补充。

每件货物最多进行一次核验，工作人员可以自行决定核验哪些货物，以及核验顺序，也可以放弃部分货物。

请你帮助仓库管理员制定一份核验计划，使最终获得的工作积分尽可能多。

输入格式

第一行包含两个正整数 (n,V)，分别表示货物数量和剩余电子校验单元的数量。

接下来 (n) 行，每行包含两个正整数 (a_i,v_i)，表示第 (i) 件货物的编号，以及完成核验后能够获得的工作积分。

输出格式

输出一个整数，表示在现有校验单元数量限制下，最多能够获得的工作积分。

输入输出样例 #1

输入

4 10
29 20
41 8
123 9
40 7

输出

16

样例解释

仓库共有 4 件货物，剩余 10 个电子校验单元。

编号为 29 的货物需要消耗 11 个校验单元，无法完成核验。

可以选择核验编号为 123 和 40 的两件货物：

• 核验 123 消耗 6 个校验单元，获得 9 点积分。
• 核验 40 消耗 4 个校验单元，获得 7 点积分。

总共消耗 10 个校验单元，获得 16 点工作积分。

可以证明，不存在获得更多工作积分的合法核验方案。

数据范围

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

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

提示

核验设备处理的是编号中的十进制数字，而不是编号本身对应的整数大小。