## 输入描述
第一行，为 2 个正整数，用一个空格隔开： N m （其中 N(<30000) 表示总钱数， m(<25) 为希望购买物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 2 个非负整数  v p （其中 v 表示该物品的价格 (#*#v\le 10000#*#) ， p 表示该物品的重要度( 1-5 )

## 输出描述
1 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<100000000) 。

## 输入样例
1000 5
800 2
400 5
300 5
400 3
200 2

## 输出样例
3900

## 提示
无