Problem : 203 - 書架

Problem Statistics

Solved Member: 16　　Submission: 94　　User Tried: 18

Statement:

FJ有N本書直立排成一列(1 <= N <= 100,000)，每本書有其高度H(i)以及寬度W(i)

FJ現在想用很多個寬度為 L (1 <= L <= 1,000,000,000)的書架將書本整理好

每次裝書都必須從1號書開始,2,3,...,直到k號裝在一個書架
然後下次再從k+1本開始裝,k+2,k+3,...
這些書的總寬度不能超過L
而這個書架的高度就是這些書當中最高那本的高度

FJ覺得全部的書架疊起來越矮、看起來越美觀

問最少的書架高度總和是多少？

Input:Output:

第 1 行有兩個用空格分開的數字，N 和 L 。

第 2 ~ N+1 行分別代表從左到右每一本書的高度 H(i) 寬度 W(i)。(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)

輸出一行，代表最少需要的書架高度總和。

Sample Input:Sample Output:

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

HINT:

一共有三個書架：
高度5 ，裝1號書(總寬度7)
高度13，裝2,3,4號書(總寬度9)
高度3 ，裝5號書(總寬度8)
全部加起來高度是21

2013.4.1題敘更改by Jack1

Source:

USACO Open 2012 Gold.

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	5000ms	131072kb
1	5000ms	131072kb	5
2	5000ms	131072kb	5
3	5000ms	131072kb	6
4	5000ms	131072kb	6
5	5000ms	131072kb	6
6	5000ms	131072kb	6
7	5000ms	131072kb	6
8	5000ms	131072kb	6
9	5000ms	131072kb	6
10	5000ms	131072kb	6
11	5000ms	131072kb	6
12	5000ms	131072kb	6
13	20000ms	131072kb	6
14	20000ms	131072kb	6
15	5000ms	131072kb	6
16	5000ms	131072kb	6
17	5000ms	131072kb	6