仓库密令（secret）

题目描述

某物资中心使用数字编号管理货物。

仓库中共有 (n) 种物资，第 (i) 种物资有一个正整数编号 $(a_i)$，重量为 $(w_i)$，价值为 $(v_i)$。

仓库按照编号的十进制数字位数决定库存数量：

• 如果编号的十进制位数为奇数，这种物资库存充足，可以选择任意非负整数件。
• 如果编号的十进制位数为偶数，这种物资只有一件，最多只能选择一次。

例如，编号 7 有 1 位数字，编号 35 有 2 位数字，编号 205 有 3 位数字。

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

求运输箱能够获得的最大总价值。

输入格式

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

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

a w v

分别表示物资编号、重量和价值。

输出格式

输出最大总价值。

输入输出样例 #1

输入

3 10
13 4 9
205 3 5
7 5 8

输出

19

样例解释

编号 13 有 2 位数字，所以最多选择一次。

编号 205 和 7 分别有 3 位和 1 位数字，因此可以重复选择。

一种最优方案是选择：

• 一件编号为 13 的物资；
• 两件编号为 205 的物资。

总重量为 (4+3+3=10)，总价值为 (9+5+5=19)。

数据范围

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