TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1738
  • 题目
  • P1738【USACO 2012 Open Gold】书架
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    有n本书,每本书有一个宽度W(i),高度H(i),(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).,现在要把书按顺序(先放1,再放2.....)放入书架,书架宽度最多是L (1 <= L <= 1,000,000,000),高度是书架中最高的书的高度,书架的数量无限制,现在求所有书架的高度和的最小值?

    输入格式

    行1: 两个整数 N and L.
    行 2..1+N: 行 i+1包含两个整数 H(i) 和W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).

    输出格式

    行 1: 所有书架高度之和的最小可能值

    样例输入

    5 10 
    5 7 
    9 2 
    8 5 
    13 2 
    3 8

    样例输出

    21

    提示

    样例解释
    分三个书架, 第一个一本书[1] (高度 5, 宽度 7), 每二个书架三本书[2\3\4] (高度13, 宽度 9), 第三个书架一本书[5] (高度 3, 宽度8).


    【数据规模】
    1 ≤ n ≤ 100000