题目描述

话说张琪曼和李旭琳又发现了一处魔法石矿， 她们有一个最多能装$\red{m}$千克的背包,现在有$\red{n}$种魔法石,每种的重量分别是$\red{W_1, W_2,...,}$ $\red{W_n,}$每种的价值分别为$\red{C_1,C_2,...,C_n}$。若每种魔法石的个数足够多,求她们能获得的最大 总价值。

输入格式

第一行为两个整数，即$\red{m,n}$。 以后每行为两个整数,表示每块魔法石的重量和价值。 $\red{1<=m,n<=200}$

输出格式

获得的最大总价值。

样例

输入样例

5 5
1 1
2 2
3 3
4 4
5 5

输出样例

5