뒤풀이

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

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

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

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

1. 모든 $i$에 대해 $L_i \le x_i \le R_i$이다.
2. $x_1 + x_2 + \cdots + x_N$이 정확히 $T$이다.
3. 모든 $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을 출력한다.