题目描述

给定一个最大载重量为 M 的卡车和 N 种食品（如食盐、白糖、大米等）。已知第 i 种食品最多拥有 w_i 公斤，商品价值为 v_i 元/公斤。请确定一个装货方案，使得装入卡车中的所有物品总价值最大。

输入格式

共 n+1 行：

• 第 1 行：两个整数 m、n，分别表示卡车最大载重量（公斤）和货物种类数。
• 接下来的 n 行：每行两个整数 w_i、v_i，分别表示该货物的拥有量（公斤）与单价（元/公斤）。

其中 1 ≤ m, n, w_i, v_i ≤ 100。

输出格式

输出一行，表示在约束下可获得的最大总价值。

输入样例 #1

100 3  
60 90  
50 100  
40 110

输出样例 #1

10300