Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
124 - ZOJ Monthly, March 2013 - G
GF And RP

Time Limit: 7 Seconds      Memory Limit: 65536 KB

A survey includes n boys(1 <= n <= 40000). Every boy has RP value rpi and the number of his girl friends gfi. (rpi, gfi) is a sequence of n ordered pairs of non-negative integers. Now you have to partition it into several contiguous groups. We suppose m is the number of these groups. The boundaries of every group are (l1, r1), (l2, r2), (l3, r3), ... , (lm, rm). It satisfies l1 = 1, rm = n, li = ri - 1 + 1, li <= ri. Ri is the maximum rp elements in the ith groups(1 <= i <= m). In the survey, for universality the sum of Ri shouldn't be more than Rlimit.

R1 + R2 + R3 + ... + Rm <= Rlimit. Rlimit is a given integer.

Gi is the sum of the number of their girl friends in ith group. For fair, I want to minimize the value

max{Gi| 1 <= i <= m}

Input

The input contains multiple test cases.

Each test case begins with a line containing 2 integers n, Rlimit(1 <= Rlimit <= 40000).

The subsequent n lines describe rpi, gfi(1 <= rpi, gfi <= 40000).

Output

For each case, print minimum max{Gi| 1 <= i <= m}.

Sample Input

4 6
4 3
3 5
2 2
2 4

Sample Output

8

Hint

2 groups: {(4, 3)(3, 5)}, {(2, 2)(2, 4)}. R1 + R2 = 4 + 2 <= Rlimit(6).

G1 = 8, G2 = 6, max(8, 6) = 8.


Author: ZHANG, Chi
Submit    Status