
ZOJ Problem Set  3692
A survey includes n boys(1 <= n <= 40000). Every boy has RP value rp_{i} and the number of his girl friends gf_{i}. (rp_{i}, gf_{i}) is a sequence of n ordered pairs of nonnegative 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 (l_{1}, r_{1}), (l_{2}, r_{2}), (l_{3}, r_{3}), ... , (l_{m}, r_{m}). It satisfies l_{1} = 1, r_{m} = n, l_{i} = r_{i  1} + 1, l_{i} <= r_{i}. R_{i} is the maximum rp elements in the ith groups(1 <= i <= m). In the survey, for universality the sum of R_{i} shouldn't be more than Rlimit. R_{1} + R_{2} + R_{3} + ... + R_{m} <= Rlimit. Rlimit is a given integer. G_{i} is the sum of the number of their girl friends in ith group. For fair, I want to minimize the value max{G_{i} 1 <= i <= m} InputThe 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 rp_{i}, gf_{i}(1 <= rp_{i}, gf_{i} <= 40000). OutputFor each case, print minimum max{G_{i} 1 <= i <= m}. Sample Input4 6 4 3 3 5 2 2 2 4 Sample Output8 Hint2 groups: {(4, 3)(3, 5)}, {(2, 2)(2, 4)}. R_{1} + R_{2} = 4 + 2 <= Rlimit(6). G_{1} = 8, G_{2} = 6, max(8, 6) = 8. Author: ZHANG, Chi Contest: ZOJ Monthly, March 2013 