TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4751
  • 题目
  • P4751过桥
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,64m
    问题描述

    一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制.

    所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.

    队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,

    我们想知道如何分批过桥能使总时间最少.

    输入格式

    第一行两个整数: w,n 分别表示 桥能承受的最大重量(100 <= w <= 400) 和 n 队员总数(1 <= n <= 16).
    接下来n 行每行两个整数t和w分别表示每个队员过桥所需时间(1 <= t <= 50) 和  该队员的重量(10 <= w <= 100).

    输出格式

    输出一个数表示最少的过桥时间.

    样例输入 1

    100 3
    24 60
    10 40
    18 50

    样例输出 1

    42

    样例输入 2

    150 5
    50 44
    40 33
    35 36
    30 75
    11 76

    样例输出 2

    90


    来源  [POI2004]PRZ