题目描述

有一个最多能装下M千克物品的背包和n件物品。第i件物品的价值为$v_i$，重量为$w_i$，每件物品都可以只取其中的一部分，取得的价值也按照所取重量的比例计算。请你选择装入背包的物品，使背包中物品的总价值最大。

输入格式

第一行输入两个整数M和n，分别表示背包的最大承重量和物品数量。

接下来n行，每行输入两个整数$v_i$和$w_i$，分别表示一件物品的价值和重量。

输出格式

输出背包能够装入物品的最大总价值，结果保留一位小数。

输入样例 1

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

输出样例 1

190.6

输入样例 2

77 1
364 309

输出样例 2

90.7

输入样例 3

317 2
442 27
885 375

输出样例 3

1126.4

数据范围

• $1\le M\le 500000$，$1\le n\le 1000$。
• $1\le v_i\le 1000$，$1\le w_i\le 500$。
• 所有输入均为整数；物品可以按任意实数比例取用。