题目描述

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

输入格式

n+1行

第一行：输入两个数分别是货车的最大载重量m(公斤)和货物的种类n

接下来n行：每行两个数，第一个是货物的拥有量wi公斤，货物的单价vi元/公斤

1≤m,n,wi,vi≤100

输出格式

一个数，最大价值

样例数据

100 3
60 90
50 100
40 110

10300