展品审核（exhibition）

题目描述

科技馆正在布置一个主题展柜。

现有 n 件不同的展品，每件展品只有一件。

第 i 件展品的重量为 wi，展示价值为 vi。

展柜最多承受 V 单位重量。

根据展览规定，最终放入展柜的展品总件数必须是偶数。

在满足重量与件数要求的情况下，求最大展示价值。

允许不选择任何展品，此时展示价值为 0。

输入格式

第一行两个整数 V,n。

接下来 nn 行，每行两个整数 wi,vi。

输出格式

输出最大展示价值。

输入样例

7 4
2 5
3 6
4 7
5 10

输出样例

15

样例解释

选择第一件和第四件展品，总重量为 2+5=7，总价值为 5+10=15。

放入的展品件数为 2，满足要求。

数据范围

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