题目描述

张琪曼和李旭琳有一个最多能装 $\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}$ 件物品的重量和价值。

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