题目背景

双十一到了，各大电商平台推出了"满减"活动。小华的信用卡额度极大，达到了 W 元。

购物车里有 N 件他心仪的商品，第 i 件商品的价格为 w_i 元。然而这些东西虽然贵，但能给小华带来的"快乐值" v_i 却很低。

小华想在不刷爆信用卡（总花费不超过 W）的前提下，获得尽可能高的总快乐值。由于价格极其庞大，用普通的计算方法电脑会直接死机，请你帮小华写一个高效的程序。

题目描述

给定信用卡额度 W 和 N 件商品，每件商品有价格 w_i 和快乐值 v_i。求在总花费不超过 W 的条件下能获得的最大总快乐值。

核心思路：由于快乐值 v_i 很小（总和不超过 1000），可以反转思路，以快乐值为容量进行 DP。

输入格式

第一行包含两个整数 W 和 N，分别表示信用卡额度和商品数量。

接下来 N 行，每行两个整数 w_i 和 v_i，分别表示第 i 件商品的价格和快乐值。

输出格式

输出一个整数，表示能获得的最大总快乐值。

样例输入

10000000 3
5000000 3
6000000 4
4000000 2

样例输出

6

样例解释 信用卡额度是 1000万。 买第 2、3 件商品，总价格为 600万 + 400万 = 1000万 ≤ 1000万，获得的快乐值为 4 + 2 = 6。

数据范围

1 ≤ W ≤ 10^9 （注意这极大） 1 ≤ N ≤ 100 1 ≤ w_i ≤ 10^7 1 ≤ v_i ≤ 10 （注意这极小，所有物品快乐值总和不会超过 1000）