TopCoder

Thumb rezero
Re Zero
Re Zero

User's AC Ratio

81.8% (18/22)

Submission's AC Ratio

50.0% (28/56)

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

Sample Output

21

Hints

你認識那個人嗎

Problem Source

HOJ

Subtasks

For Testdata: 0 ~ 19, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536
10 1000 65536
11 1000 65536
12 1000 65536
13 1000 65536
14 1000 65536
15 1000 65536
16 1000 65536
17 1000 65536
18 1000 65536
19 1000 65536