Background

过几天,丁丁的学校要组织一次秋游的活动,学校要求每个学生准备一个背包，背包里可以放入必要的生活物品及零食,这可把丁丁高兴坏了,现在丁丁准备了一个背包,背包容量是$M(O<M≤200)$，有$N(1<N≤1000)$个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量,聪明的你能帮丁丁解决问题吗?

Input

第1行有两个数，$M$和$N$；

第2行到$N+1$行：第$i$行为第$i-1$个物品的价值和质量（均为小于$100$的正整数），中间用空格隔开。

Output

只有一个数为最大总价值（保留一位小数）。

Samples

150 7
10 35
40 30
30 60
50 50
35 40
40 10
30 25

190.6

Limitation

1s, 1024KiB for each test case.