Informatica Online Judge

  건초더미 저녁식사 [2171 / 087B]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 9   Total Tried : 13


The Champion of this Problem (C++) : gs17003 - 0ms / 659byte
My Best Submission (C++) : N/A

[USACO (Christopher Chang & Allen Chen)]

Background

농부 존은 젖소들을 위해서 N개의 건초더미를 이용하여 맛있는 저녁식사를 준비중이다.

각 건초더미들 중 $i$번째 건초더미의 맛은 $F_i$, 매운 정도는 $S_i$의 값을 가진다.

저녁식사는 1개 이상으로 이루어진 연속된 구간의 건초더미들을 먹는 것이다. (농부 존은 원래 주어진 건초더미들의 순서를 바꾸지 않는다.)

저녁식사의 맛은 먹은 구간의 각 건초더미들의 맛의 합으로 정의한다.

저녁식사의 매움은 먹은 구간의 각 건초더미들의 매운 정도 중 가장 매운 것으로 정의한다.

농부 존은 적어도 맛이 $M$이상인 식사를 제공하려고 한다. 제공할 수 있는 식사 중 매움을 최소로 하려고 할 때, 최소 매움을 구하는 프로그램을 작성하시오.

Input

$N$ $M$
$F_1$ $S_1$
$F_2$ $S_2$
:
$F_n$ $S_n$

[입력값의 정의역]
$1 ≤ N ≤ 100,000$
$1 ≤ F_i, S_i ≤ 100,000,000 (10^9)$
$1 ≤ M ≤ 1,000,000,000,000,000,000 (10^{18})$

Output

제공할 수 있는 조건을 만족하는 식사들 중 가장 적은 매움의 값을 구하여 출력한다.

IO Example

입력
5 10
4 10
6 15
3 5
4 9
3 6

출력
9

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]