시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 249 81 75 42.614%

문제

도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.

하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.

도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지(Li)와, 어느 정도 마시면 힘든지(Ri)를 물어보았다. 각 사람은 Li미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri를 초과하는 술을 마시면 천국으로 가버릴 수도 있다. 도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.

그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다. 마침 도현이의 통장엔 정확히 T의 술을 살 수 있는 금액이 들어 있었고, 도현이는 정확히 T의 술을 결제하였다.

이제 도현이는 모든 사람 i에게 Li이상 Ri이하의 술을 주면서, 그 총합이 정확히 T가 되도록 술을 분배하려고 한다. 하지만 안타깝게도, 사람들은 자신의 주량을 과대평가하는 경향이 있다. 이에 따라 도현이는 S의 값을 정하고, 각 사람에게 그 사람이 원하는 술의 양이 얼마이던지 관계없이 S이하의 술만을 주려고 한다. 이제 도현이는 술도 결제했고, 주량도 조사했으므로,

  1. 모든 사람 i가 Li이상 Ri이하의 술을 받으면서,
  2. 모든 사람이 받은 술의 총합이 정확히 T가 되고,
  3. 어떤 사람도 S를 초과하는 술은 받지 않게 할 수 있는,

그러한 S값만 결정하면 된다.

도현이를 도와 조건을 만족하는 S값을 찾아주도록 하자.

만약 그런 값이 여러 개라면, 도현이는 그 중 가장 작은 값을 찾고 싶다.

입력

첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109)

둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106)

출력

만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력한다.

문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.

예제 입력 1

3 10
2 5
4 10
1 3

예제 출력 1

4