문제
플라톤은 “아카데미아”라는 교육 기관을 세우면서 “기하학을 모르는 자는 이곳에 들어오지 말라”라는 글귀를 남긴 것으로 유명하다.
사실 플라톤은 이를 조금 더 명확하게 하기 위해서 아카데미아에 N개의 반을 만들어놓고 각 반에 아래와 같은 글귀를 남겼다.
▷ 기하학 실력이 Gk 미만인 자는 이곳에 들어오지 말라.
아카데미아의 k번째 반에서 수업을 듣다 보면 기하학 실력이 Ak가 된다.
학생이 수업을 듣기 전에 기하학 실력이 Ak보다 높았었다고 해도 수업을 들은 후에는 기하학 실력이 Ak가 됨에 유의하여라.
학생인 진서스토텔레스는 현재 기하학 실력이 G0인데,
진서스토텔레스는 오직 기하학에만 열정을 쏟아붓는 열정적인 학생이기 때문에,
아카데미아에 들어가서 수업을 들으면서 자신의 기하학 실력을 최대 수치로 끌어올리려고 한다.
진서스토텔레스는 아카데미아의 각 반의 Gk값과 Ak값을 알고 있다.
이 때 아카데미아의 수업을 몇 개 들은 후 진서스토텔레스의 기하학 실력으로 가능한 최댓값을 구하여라.
[서브태스크]
서브태스크 1 : 1 ≤ N ≤ 1,000
서브태스크 2 : 1 ≤ G0, Gk, Ak ≤ 500
서브태스크 3 : Gp < Gq 인 모든 p, q에 대하여 Ap ≤ Aq 를 만족한다. 또한, G값은 오름차순으로 주어진다.
서브태스크 4 : 추가적인 제약조건은 없다
입력
첫 번째 줄에는 반의 수 N과 진서스토텔레스의 현재 기하학 실력 G0이 주어진다. 1 ≤ N ≤ 400,000, 1 ≤ G0 ≤ 109 두 번째 줄부터 N개의 줄에는 아카데미아의 각 반의 Gk 값과 Ak 값이 주어진다. 1 ≤ Gk < Ak ≤ 109
출력
아카데미아의 수업을 몇 개 들은 후 진서스토텔레스의 기하학 실력으로 가능한 최댓값을 출력한다.
예제
3 5
3 7
9 21
6 8
8.
로그인해야 코드를 작성할 수 있어요.