뒤풀이

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 참가자 i가 [L_i, min(R_i, S)] 범위의 정수를 받고 그 합이 정확히 T가 되는 가장 작은 상한 S를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 이분 탐색, 배열, 수학
정답자: 아직 제출이 없습니다

문제

도현이는 대회가 끝난 뒤 뒤풀이를 하려고 술집을 예약했다. 사장님은 술을 $T$ 만큼 팔아야 예약을 받아주겠다고 했고, 도현이는 딱 $T$ 만큼의 술값을 미리 결제했다.

도현이는 참가자 $N$ 명에게 어느 정도 마시면 좋은지 미리 물어보았다. $i$ 번 참가자는 $L_i$ 보다 적게 마시면 양이 모자라 기분이 좋지 않고, $R_i$ 보다 많이 마시면 몸이 상한다. 그래서 도현이는 $i$ 번 참가자에게 $L_i$ 이상 $R_i$ 이하의 술을 주어야 한다.

사람들은 자기 주량을 부풀려 말하는 편이다. 그래서 도현이는 상한 $S$ 를 하나 정하고, 그 사람이 말한 양이 얼마든 누구에게도 $S$ 를 넘는 양은 주지 않으려고 한다.

$i$ 번 참가자가 받는 양을 $x_i$ 라고 할 때, 다음 세 조건을 모두 만족하는 $S$ 를 찾아야 한다.

모든 $i$ 에 대해 $L_i \le x_i \le R_i$ 이다.
$x_1 + x_2 + \cdots + x_N$ 이 정확히 $T$ 이다.
모든 $i$ 에 대해 $x_i \le S$ 이다.

$x_i$ 와 $S$ 는 모두 정수이다. 조건을 만족하는 $S$ 가 여러 개라면 그중 가장 작은 값을 구한다.

입력

첫째 줄에 참가자 수 $N$ 과 술의 총량 $T$ 가 주어진다. ( $1 \le N \le 1\,000$ , $1 \le T \le 10^9$ )

둘째 줄부터 $N$ 개의 줄에 걸쳐 $i$ 번 참가자의 $L_i$ 와 $R_i$ 가 공백으로 구분되어 주어진다. ( $1 \le L_i \le R_i \le 10^6$ )

출력

조건을 만족하는 $S$ 가 있으면 그중 가장 작은 값을 첫째 줄에 출력한다.

$S$ 를 어떻게 정해도 조건을 만족하는 분배가 없으면 첫째 줄에 -1을 출력한다.

예제1

예제 1
입력
```
3 10
2 5
4 10
1 3
```
예상 출력
```
4
```