Description

给定一个最大载重量为M的卡车和N种食品， (假设它们都是散装且大货车只受重量限 制不受体积限制)。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程 确定一个装货方案，使得装入卡车中的所有物品总价值最大。

Format

Input

第一行：输入两个数分别是货车的最大载重量m(公斤)和货物的种类n
接下来n行：每行两个数，第一个是货物的拥有量wi公斤，货物的单价vi元/公斤
1≤m,n,wi,vi≤200

Output

一个数，最大价值

Samples

100 3
60 90
50 100
40 110

10300

Limitation

1s, 1024KiB for each test case.