夜间运输（transport）

题目描述

某物流公司准备安排一次夜间运输。

共有 n 件货物，每件货物都只能运输一次。

第 i 件货物的重量为 $w_i，运输收益为 v_i$。

运输车辆最大承重为 VV。

由于运输通道的特殊检测要求，本次运输的货物总重量必须为奇数。

在总重量不超过 V 的条件下，求能够获得的最大运输收益。

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

输入格式

第一行两个整数 V,n。

接下来 nn 行，每行输入 wi,vi。

输出格式

输出最大运输收益，无解输出 -1。

输入样例

9 4
2 6
3 7
4 10
5 11

输出样例

23

样例解释

选择前三件货物，总重量为 2+3+4=9，是奇数，且没有超过运输车辆的最大承重。

获得收益 6+7+10=23。

数据范围

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