当前没有测试数据。

书接上文

俩活宝因为太菜了，只能请一个护航了……

可惜武将不识数，护航橄榄球僵尸根本不会理包，于是他决定一个个试试，看看怎样能带出最多价值

详情说明

橄榄球僵尸给他俩带了个大包，大包有$m$格（$m$最高可达$100$），同时给他们清图了，获得了$n$个物品

他列出了每个物品的价值$w_i$和所占格数$c_i$

现在，他要求出他能够带出的最大价值为多少

输入格式

第一行，两个数$m,n$（保证$2\leq n,m \leq 20$）

接下来n行，每行2个数，分别表示$w_i 和c_i$

输出

一个数，表示最大可带出的价值

样例

2 2
1 2
2 1

2