Background

Special for beginners, ^_^

Description

有一个背包，背包容量是M（ 0<=M<=200），有N（1<=N<=1000）物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过背包总容量。

Format

Input

第一行有两个数，M和N。 第二行到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.