4.生日礼物 (gift)

【问题描述】

  Kobe有N元钱，M个商品可以选择，每个商品有一定的价格P。他对每个商品有不同的满意度F，希望在花费不超过N元的情况下，使得买到的商品的满意度总和最大。

【输入文件】

  第一行为N，第二行为M

第三行到第M+2行为两个数，分别为商品的价格P和满意度F

【输出文件】

 买到的商品的最大满意度总和.

【样例输入】

47.13

4

17.11 2

11.48 1

18.42 2

30.01 2

【样例输出】

5

【数据规模】

对于40%的数据有：

0<=N<=100且N小数点后有两位小数

1<=M<=100

对于100%的数据有：

0<=N<=10000且N小数点后有两位小数

1<=M<=10000

1<=F<=2且F为整数

0<=P<=100且P小数点后有两位小数