分类调配（classify）

题目描述

某研究中心准备采购一批设备。

共有 (n) 台不同的设备，每台设备拥有一个正整数编号 $(a_i)、重量 (w_i) 和使用价值 (v_i)$。

研究中心按照设备编号中的最大十进制数字划分设备等级。

例如：

• 编号 205 的最大数位是 5；
• 编号 483 的最大数位是 8；
• 编号 111 的最大数位是 1。

为了避免同等级设备之间出现兼容问题，同一个等级最多只能选择一台设备。

不同等级的设备可以同时选择。

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

求在总重量不超过 (V) 的条件下，能够获得的最大总价值。

输入格式

第一行包含两个整数 (n,V)。

接下来 (n) 行，每行包含三个整数：

a w v

输出格式

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

输入输出样例 #1

输入

5 7
12 2 5
20 3 8
43 4 9
54 3 7
65 2 3

输出

17

样例解释

编号 12 和 20 的最大数位都是 2，因此属于同一个等级，最多只能从中选择一台。

编号 43 的最大数位是 4。

编号 54 的最大数位是 5。

编号 65 的最大数位是 6。

选择编号为 20 和 43 的设备，总重量为 (3+4=7)，总价值为 (8+9=17)。

数据范围

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