特殊藏品（collection）

题目描述

某博物馆准备从 (n) 件藏品中选择若干件进行展览。

第 (i) 件藏品具有一个编号 (a_i)、重量 (w_i) 和展示价值 (v_i)。

每件藏品只有一件，最多只能选择一次。

博物馆按照藏品编号进行特殊分类：

如果一个编号的所有十进制数字之和为奇数，则称该藏品为特殊藏品；否则称为普通藏品。

展览要求：

1. 所有选中藏品的总重量不超过 (V)。
2. 选中的特殊藏品件数必须是奇数。
3. 展示总价值尽可能大。

如果不存在合法方案，输出 -1。

输入格式

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

接下来 (n) 行，每行输入三个整数：

a w v

输出格式

输出最大总价值，无解输出 -1。

输入输出样例 #1

输入

4 7
12 2 5
24 3 6
111 4 10
80 5 9

输出

16

样例解释

编号 12 的数位和为 3，是特殊藏品。

编号 111 的数位和也为 3，是特殊藏品。

编号 24 和 80 的数位和均为偶数，是普通藏品。

可以选择编号为 111 和 24 的藏品：

• 总重量：(4+3=7)
• 总价值：(10+6=16)
• 选中的特殊藏品件数：1

满足全部条件。

数据范围

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