1811 . 書架
TopCoder
Tags
Description
猥瑣的那個人有N本小黃書直立排成一列(1 <= N <= 100,000)，每本書有其高度H(i)以及寬度W(i)
但是猥瑣的那個人想用很多個寬度為 L (1 <= L <= 1,000,000,000)的書架將書本整理好
每次裝書都必須從1號書開始,2,3,...,直到k號裝在一個書架
然後下次再從k+1本開始裝,k+2,k+3,...
這些書的總寬度不能超過L
而這個書架的高度就是這些書當中最高那本的高度
那個人覺得全部的書架疊起來越矮、看起來越美觀
問最少的書架高度總和是多少？
Input Format
第 1 行有兩個用空格分開的數字，N 和 L 。
第 2 ~ N+1 行 分別代表從左到右每一本書的高度 H(i) 寬度 W(i)。(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)
Output Format
輸出一行，代表最少需要的書架高度總和。
Sample Input
5 10
5 7
9 2
8 5
13 2
3 8
5 7
9 2
8 5
13 2
3 8
Sample Output
21
Hints
你認識那個人嗎
Problem Source
HOJ
Subtasks
For Testdata: 0 ~ 19, Score: 100
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) |
|---|---|---|---|
| 0 | 1000 | 65536 | 262144 |
| 1 | 1000 | 65536 | 262144 |
| 2 | 1000 | 65536 | 262144 |
| 3 | 1000 | 65536 | 262144 |
| 4 | 1000 | 65536 | 262144 |
| 5 | 1000 | 65536 | 262144 |
| 6 | 1000 | 65536 | 262144 |
| 7 | 1000 | 65536 | 262144 |
| 8 | 1000 | 65536 | 262144 |
| 9 | 1000 | 65536 | 262144 |
| 10 | 1000 | 65536 | 262144 |
| 11 | 1000 | 65536 | 262144 |
| 12 | 1000 | 65536 | 262144 |
| 13 | 1000 | 65536 | 262144 |
| 14 | 1000 | 65536 | 262144 |
| 15 | 1000 | 65536 | 262144 |
| 16 | 1000 | 65536 | 262144 |
| 17 | 1000 | 65536 | 262144 |
| 18 | 1000 | 65536 | 262144 |
| 19 | 1000 | 65536 | 262144 |