건초 더미 만찬

면접 대비

시간 제한2초메모리 제한512 MB

요약

맛의 합이 M 이상인 연속 구간 중에서 구간 최대 매운맛이 가장 작은 값을 찾는다.

난이도: 보통10점 중 6점
유형: 투 포인터, 슬라이딩 윈도우, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

농부 존이 소들에게 줄 맛있는 식사를 준비한다. 헛간에는 건초 더미가 $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}$ ) 이상이어야 한다는 조건에서, 코스 하나로 이루어진 식사가 얻을 수 있는 매운맛의 최솟값을 구하라.

입력

첫째 줄에 건초 더미의 개수 $N$ 과 식사가 만족해야 하는 최소 총 풍미 $M$ 이 정수로 주어진다. 다음 $N$ 개 줄에 건초 더미의 정보가 한 줄에 두 정수씩, 풍미 $F$ 와 매운맛 $S$ 순으로 주어진다.

출력

최소 총 풍미 조건을 만족하는 코스 하나짜리 식사의 매운맛 최솟값을 한 줄에 출력한다. 조건을 만족하는 식사는 항상 하나 이상 존재한다.

예제3

예제 1
입력
```
5 10
4 10
6 15
3 5
4 9
3 6
```
예상 출력
```
9
```
예제 2
입력
```
1 1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
8 1
5 8
1 3
9 7
2 1
4 6
7 2
3 9
6 5
```
예상 출력
```
1
```