双类装箱（package）

题目描述

某实验室准备将一批仪器装入运输箱。

现有 n 件不同的仪器，每件只能放入一次。

第 i 件仪器的重量为 $w_i，价值为 v_i$。

运输箱最大承重为 V。

为了满足检测要求，运输箱中必须同时包含：

• 至少一件重量为奇数的仪器；
• 至少一件重量为偶数的仪器。

在总重量不超过 V 的情况下，求可以获得的最大总价值。

如果不存在符合要求的装箱方案，输出 -1。

输入格式

第一行两个整数 V,n。

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

输出格式

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

输入样例

10 4
3 6
4 9
5 10
2 4

输出样例

20

样例解释

选择重量为 3、5、2 的三件仪器。

总重量为 10，既包含奇数重量仪器，也包含偶数重量仪器。

总价值为 6+10+4=20。

数据范围

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