RiseOJ – 건초 더미 만찬

설명

농부 존이 소들을 위해 맛있는 식사를 준비하고 있다! 그의 헛간에는 $$N$$ 개의 건초 더미 ( $1 \le N \le 100,000$ )가 있다. $$i$$ 번째 건초 더미에는 맛 $$F_i$$ ( $1 \le F_i \le 10^9$ )와 매운 정도 $$S_i$$ ( $1 \le S_i \le 10^9$ )가 있다.

식사는 단일 코스로 이루어지며, 하나 이상의 연속한 건초 더미를 포함하는 연속 구간이다 (농부 존은 건초 더미의 순서를 바꿀 수 없다). 식사의 총 맛은 구간에 속한 맛들의 합이다. 식사의 매운 정도는 구간에 속한 모든 건초 더미의 매운 정도 중 최댓값이다.

농부 존은 식사의 총 맛이 적어도 $$M$$ ( $1 \le M \le 10^{18}$ )은 되어야 한다는 조건 아래, 단일 코스 식사의 매운 정도가 최소 얼마까지 될 수 있는지 알고 싶어한다.

Problem credits: Christopher Chang and Allen Chen

제약

Problem credits: Christopher Chang and Allen Chen

입력 형식

첫째 줄에 정수 $$N$$ 과 $$M$$ 이 주어지는데, 각각 건초 더미의 수와 식사가 가져야 하는 최소 총 맛이다. 다음 $$N$$ 개의 줄에 $$N$$ 개의 건초 더미에 대한 정보가 한 줄에 두 정수씩 주어지는데, 먼저 맛 $$F$$ , 그 다음 매운 정도 $$S$$ 이다.

출력 형식

최소 맛 조건을 만족하는 단일 코스 식사의 최소 매운 정도를 출력한다. 맛 조건을 만족하는 단일 코스 식사는 항상 적어도 하나 존재한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 hayfeast.in · 출력을 쓸 파일 hayfeast.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Gold

올림피아드 > USACO > 2017-2018 > December > Gold

태그

JudgeUSACO

건초 더미 만찬

평가 및 의견

풀이 제출