X神的书架

提交数: 35, 通过率: 42.86%, 平均分: 62.09

题目描述:

由于X神是在是太学霸了,他有许多的书,每本书有高度与重量。他要把这些书按顺序放在一些书架上。每个书架上是序号连续的若干本书。但书架有最大承重。各个书架的不美观程度等于,书架上最高的那本书的高度。现在为了考验你们,他决定让你们搞定一个问题:在所有的书都被安置的情况下,最小的不美观程度之和是多少。(书架个数无限制)

输入格式:

两个空格隔开的数字n,maxW表示有多少本书与书架的最大承重

接下来n行,第i行 两个空格隔开的数字表示序号为i的书的高度与重量

输出格式:

一个整数表示最小的不美观程度之和

样例输入:

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

样例输出:

21

提示:

输入输出均不大于2^50

20% n<=100

40% n<=10000

100% n<=100000

数据逐渐增大

 

时间限制: 1000ms
空间限制: 256MB