问题描述

具体描述见教材p129： 有一个背包，背包的容量是M(0<M<=200)，有N(1<N<=1000)个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品价值最大，但不能超过总容量。

格式

输入

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

输出

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

样例

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

190.6

限制

1s, 64MB.