装箱验收（inspection）

题目描述

某物流中心需要准备一批特殊物资。

仓库中共有 (n) 种物资，第 (i) 种物资的重量为 $(w_i)，价值为 (v_i)$。

在装箱前，仓库会将所有物资按重量从小到大排序，并从 1 开始重新编号。

如果重量相同，则按照输入顺序排列。

根据仓库的库存规定：

• 重新编号为奇数的物资，最多只能选择一件。
• 重新编号为偶数的物资，可以选择任意非负整数件。

此外，运输箱的验收系统规定：所有选中物资的总价值必须是奇数。

运输箱最大承重为 (V)。

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

如果无法满足验收要求，输出 -1。

输入格式

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

接下来 (n) 行，每行输入两个整数 $(w_i,v_i)$。

输出格式

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

输入输出样例 #1

输入

4 10
5 9
2 3
4 7
3 5

输出

17

样例解释

排序后，重量为 3 的物资重新编号为 2，因此可以重复选择。

重量为 4 的物资重新编号为 3，因此最多选择一件。

选择两件重量为 3、价值为 5 的物资，以及一件重量为 4、价值为 7 的物资：

总重量为 (3+3+4=10)。

总价值为 (5+5+7=17)，满足总价值为奇数的条件。

数据范围

• $(1\le n\le100)$
• $(1\le V\le2000)$
• $(1\le w_i\le2000)$
• $(1\le v_i\le10000)$

统一说明

所有题目采用标准输入输出。

不同物品即使重量相同，也视为不同物品。每件物品或每种物资的可选择次数，以对应题目的具体规定为准。

建议时间限制：1～2 秒。

建议空间限制：128 MB。