34987번 - 급식 뭐 먹지

문제

대전대신고등학교 영양사 선생님은 오늘도 학생들을 위한 급식 메뉴를 만들고 있다. 급식 메뉴는 맛 수치와 영양 수치를 가지며 초기에 두 수치는 모두 0ドル$이다. 영양사 선생님은 마법의 주문이라는 특별한 능력이 있으며, 마법의 주문을 사용할 때마다 맛 수치 혹은 영양 수치를 1ドル$ 증가시킬 수 있다. 마법의 주문은 최대 $M$번까지 사용할 수 있다.

학생들은 각자 음식에 대한 취향이 있어 급식 메뉴가 취향에 맞을 때만 먹는다. 구체적으로 $N$명의 학생 중 $i$번째 학생은 맛 수치가 $a_i,ドル 영양 수치가 $b_i$ 이상일 때만 급식을 먹는다.

학생들의 까다로운 취향 때문에 영양사 선생님은 마법의 주문을 어떻게 사용할지 어려움을 겪고 있다. 영양사 선생님을 도와 마법의 주문을 최대 $M$번 사용해 급식을 먹는 학생 수를 최대화하자.

입력

첫번째 줄에 $N,M$가 공백으로 구분되어 주어진다. $(1 \le N \le 10^5;$ 0ドル \le M \le 10^6)$

두번째 줄부터 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $a_i, b_i$가 공백으로 구분되어 주어진다. $(0 \le a_i, b_i \le 10^6)$

출력

첫번째 줄에 급식을 먹는 학생 수의 최댓값을 출력한다.

제한

노트