### 问题描述 在某游戏中，存在一座「迷宫之塔」的古老建筑。迷宫中的各个房间充满了各种机关、怪物和宝藏，用户打败房间内的怪物可以获得对应的宝藏。玩家在进入塔内之前，系统会发放一张迷宫地图，这张地图上标有每个房间的入口、打败怪物需要的魔法值和对应的宝藏。用户面临的问题如下：只能根据地图描述的路线进行，用户可根据路线选择是否进入房间打怪；用户的魔法值固定，每进行一轮战斗就会消耗房间对应的魔法值。据上述描述，请设计算法使用户宝藏最大化。 ### 输入格式 第一行输入一个正整数，代表魔法值 $v$； 第二行输入一个正整数，代表房间数量 $n$； 接下来的 $n$ 行，每行包括两个正整数，表示打败房间怪物需要的魔法值和房间对应的宝藏价值。 ### 输出格式 输出仅一行，包含一个正整数，表示答案。 ### 样例输入 ```c++ 500 5 50 100 100 200 150 300 200 400 250 500 ``` ### 样例输出 ``` 1000 ``` ### 说明 初始魔法值 $500$，共有 $5$ 个房间。打败第一个房间的怪物所需魔法值 $50$，可获得宝藏奖励 $100$，此时剩余魔法值 $450$，累计宝藏值 $100$；打败第二个房间的怪物所需魔法值 $100$，可获得宝藏奖励 $200$，此时剩余魔法值 $350$，累计宝藏值 $300$；打败第三个房间的怪物所需魔法值 $150$，可获得宝藏奖励 $300$，此时剩余魔法值 $200$，累计宝藏值 $600$；打败第四个房间的怪物所需魔法值 $200$，可获得宝藏奖励 $400$，此时剩余魔法值 $0$，累计宝藏值 $1000$。 ### 评测数据规模 $1\le v\le1000 , 1\le n\le1000, 1\le v_i\le1000, 1\le w_i\le1000 $