题目描述

张琪曼和李旭琳有一个最多能装$\red{m}$千克的背包,有$\red{n}$块魔法石,它们的重量分别是 $\red{W_1,W_2,..,W_n,}$它们的价值分别为$\red{C_1,C_2,...,C_n.}$若每种魔法石只有一件,问能装人的最 大总价值。

输入格式

第一行为两个整数$\red{m}$和$\red{n,}$以下$\red{n}$行中，每行两个整数$\red{W_i,C_i}$分别代表第$\red{i}$件物品的重 量和价值。

输出格式

输出一个整数,即最大价值。

样例

输入样例

8 3
2 3
5 4
5 5

输出样例

8

数据范围

$\red{m<=200,n<=30}$