TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1200
  • 题目
  • P1200Pugna大战何老板2.0
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Pugna拿了一血过后,升到7级,点满了技能幽冥守卫。然后走到哪放到哪,和他对线的何老板的Pudge被折磨得飘飘欲仙,欲仙欲死~眼看着自己才213的魔法,连钩子都不能扔几下,还被Pugna的守卫限制了魔法回复速度,自己又没有打多少钱出装备……这时,机智的何老板看到队友用他开了共享的小鸡买了神装,正准备送过去……机智的何老板马上关闭了共享,自己把那些东西卖了。现在他有很多钱了。。。
    我们假设何老板只知道可以买n种东西。比如分别是57块的树枝,150块的斗篷,450块的披风和1000块的法杖,分别可以加1,3,6,10点的智力,但是DOTA里面最多只能买6种物品。比如现在有2000块,那么可以买一根1000的法杖,一个450的披风,三个150的斗篷和一根57的树枝。总共可以获得10+6+3+3+3+1=26的智力,花费1957。还有更好的方法就是3个披风和3个斗篷,可以花1800就有27智力。机智的何老板想设计一个程序帮他算算在买得起的情况下最多能增加多少的智力。(Pugna注:如果本人有点智力的话是绝对不会去堆智力的。。。当然这和本题无关)

    输入格式

    共n+1行
    第一行,两个整数,X和n,表示拥有的钱数和何老板知道的可以买的物品的总数
    接下来n行,每行2个整数Oi和wi,分别表示价格和获得的智力加成

    输出格式

    一个整数,为最大可以增加的智力值

    样例输入

    2000 6
    57 1
    150 3
    450 6
    500 0
    1000 10
    2100 10

    样例输出

    27

    提示

    数据范围:
    0<n<=100
    0<X<=5000
    0<Oi<=5000
    -50<=wi<=50


    来源  有问题找铺盖