金明有N元买m个物品，使每件物品的价值（价值=价格*重要度）总和最大。

设第j件物品的价格为v[j]，重要度为w[j]

N  m（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）

从第2行到第m+1行，每行有2个非负整数

v[j]，w[j]

（其中v表示该物品的价格(v<=10000)，w表示该物品的重要度(1~5)）

输出只有一个正整数，为不超过总钱数的物品的价值总和的最大值（<100000000）。