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

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

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

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

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

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

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

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

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

입력 형식

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

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

출력 형식

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

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

예제 입력

3 10
2 5
4 10
1 3

예제 출력

4