题目描述

每件物品最多选择一次。在容量为 V 的背包中，选择若干物品，使总重量不超过 V，并使总价值最大。

输入格式

第一行 V,N，随后 N 行，每行两个正整数，分别表示一件物品的重量和价值。

输出格式

输出最大总价值。

样例

10 3
6 12
5 10
4 8

20

数据范围

1≤V≤200，1≤N≤30，物品重量和价值均为1至10000的整数。