数字货箱（cargo）

题目描述

某仓库有 (n) 件特殊货物，每件货物都有一个正整数编号 $(a_i) 和价值 (v_i)$。

这些货物没有直接标注重量，而是按照编号计算运输重量：

一件货物的重量，等于它的编号中所有十进制数字之和。

例如，编号为 305 的货物，其重量为：

3+0+5=8

每件货物只有一件，最多只能选择一次。

现在有一个最大承重为 (V) 的运输箱。

请计算在所有选中货物的总重量不超过 (V) 的条件下，能够获得的最大总价值。

输入格式

第一行包含两个整数 (n,V)，分别表示货物数量和运输箱容量。

接下来 (n) 行，每行包含两个整数$(a_i,v_i)$，表示货物编号和价值。

输出格式

输出一个整数，表示最大总价值。

输入输出样例 #1

输入

4 9
23 7
41 9
111 6
40 8

输出

17

样例解释

四件货物的重量分别为：

选择编号为 41 和 40 的货物，总重量为 (5+4=9)，总价值为 (9+8=17)。

数据范围

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