封箱验收（inspection）

题目描述

某物流中心正在进行最终装箱验收。

运输箱的最大承重为 V，共有 n 种货物。

第 i 种货物的重量为 $w_i，价值为 v_i$。

仓库的供货规则如下：

• 重量为奇数的货物，可以选择任意非负整数件。
• 重量为偶数的货物，最多只能选择一次。

除此之外，验收系统还要求：所有装入货物的总价值必须为奇数。

在总重量不超过 V 的前提下，求能够获得的最大总价值。

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

输入格式

第一行输入两个整数 V,n。

接下来 n 行，每行输入 $w_i,v_i$。

输出格式

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

输入样例

10 3
3 5
4 7
5 8

输出样例

17

样例解释

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

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

总价值为 5+5+7=17，是奇数，满足要求。

数据范围

• 1≤n≤100
• 1≤V≤2000
• 1≤wi≤2000
• 1≤vi≤10000