TopCoder

Caido

$\text{W}ai\text{M}ai\sim$

User's AC Ratio

78.6% (33/42)

Submission's AC Ratio

36.5% (57/156)

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

Hints

你認識那個人嗎

Problem Source

HOJ

Subtasks

No.	Testdata Range	Score
1	0~20	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	262144	1
1	1000	65536	262144	1
2	1000	65536	262144	1
3	1000	65536	262144	1
4	1000	65536	262144	1
5	1000	65536	262144	1
6	1000	65536	262144	1
7	1000	65536	262144	1
8	1000	65536	262144	1
9	1000	65536	262144	1
10	1000	65536	262144	1
11	1000	65536	262144	1
12	1000	65536	262144	1
13	1000	65536	262144	1
14	1000	65536	262144	1
15	1000	65536	262144	1
16	1000	65536	262144	1
17	1000	65536	262144	1
18	1000	65536	262144	1
19	1000	65536	262144	1
20	1000	65536	262144	1

Submit

Status

Ranklist

1811 . 書架