描述

小方小块小鸟经过千辛万苦终于打败了宝藏海湾的海盗，进入了他们的藏宝洞。大战过后，他们力气都用得差不多了，最多只能背得动 $total$ 克的战利品离开。

在他们的面前有 $n$ 块海盗们搜刮回来的金块。海盗们为了好管理，已经把金块的总重量 $weight$ ( $1 ≤ weight < 100$ )、价值 $value$ ( $1 ≤ value < 100$ ) 都标在了每个金块旁边。

现在需要你帮小方小块小鸟计算出，最大能带走多少价值的黄金？

输入输出格式

第一行为一个正整数 $total$ ，表示最多携带的重量； ( $1 ≤ total ≤ 10000$ )

第二行为一个正整数 $n$ ，表示有几个金块；( $1≤ n ≤ 100$ )

随后 $n$ 行，每行两个以空格分割的正整数 $weight$ 、 $value$ ，分别表示每堆金块的总重量和价值。( $1≤ weight ≤ 100$ , $1 ≤ value < 100$ )

一个正整数，表示他们能带走黄金的最大价值。