物资调配（supply）

题目描述

某物资中心正在准备一批救援物资。

运输箱的最大承重为 V，仓库中共有 n 种物资。第 i 种物资的重量为 $w_i，价值为 v_i$。

根据仓库的库存管理规定：

• 重量为奇数的物资，库存充足，可以选择任意非负整数件。
• 重量为偶数的物资，库存只有一件，最多只能选择一次。

要求放入运输箱的物资总重量不超过 VV。

请计算能够获得的最大总价值。

输入格式

第一行两个整数 V,n。

接下来 nn 行，每行两个整数 $w_i,v_i$。

输出格式

输出一个整数，表示最大总价值。

输入样例

10 3
3 5
4 9
5 8

输出样例

19

样例解释

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

总重量为 4+3+3=10，总价值为 9+5+5=19。

数据范围

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