수강신청

이번 학기에 개설되는 과목들을 살펴보던 달구는 수강을 희망하는 $N$개의 과목을 추려냈다. 야망 넘치는 달구는 이번 학기에 최대한 많은 과목을 수강하고자 한다. 이를 위해 수강을 희망하는 $N$개 과목의 수강 정원과 수강 희망자 수를 조사했다. $i$번째 과목의 수강 정원은 $a_i$명이고, 해당 과목의 수강 희망자 수는 달구를 포함하여 $b_i$명이다. 달구가 다니는 학교의 전교생 수는 달구를 포함하여 $M$명이다. 각 학생은 초당 최대 한 개의 과목에만 수강신청을 할 수 있다. 여러 명의 학생이 같은 과목에 동시에 수강신청을 하더라도, 달구는 반드시 그 과목에 먼저 신청할 수 있다. 수강신청은 선착순으로 진행되며, 수강 정원이 가득 찬 과목에는 더 이상 신청할 수 없다. 달구가 조사한 수강 희망자 외의 학생은 해당 과목에 수강신청을 하지 않는다. 달구는 수강신청 전에 $N$개 과목에 서로 다른 우선순위를 미리 정해 두고, 우선순위가 높은 순서대로 과목에 수강신청을 하려고 한다. 우선순위가 더 높은 과목의 정원이 모두 찼다면 그 과목은 신청하지 않고 다음 우선순위의 과목에 신청한다. 수강신청 도중에는 상황에 따라 우선순위를 바꿀 수 없다. 다른 학생들의 신청 순서에 따라 달구가 수강할 수 있는 과목 수가 크게 달라질 수 있다. 따라서 달구는 가능한 모든 우선순위 중에서, 다른 학생들의 신청 순서가 최악인 경우에도 가장 많은 과목을 수강할 수 있는 우선순위를 정하려고 한다. 각 과목의 우선순위를 최선으로 배정했을 때, 다른 학생들의 신청 순서가 최악인 경우에 달구가 수강할 수 있는 과목 수를 구하라.

첫 번째 줄에 달구가 수강을 희망하는 과목의 개수 $N$과 달구를 포함한 전교생의 수 $M$이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 100000)$ 이후 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 과목의 수강 정원 $a_i$와 달구를 포함한 수강 희망자 수 $b_i$가 공백으로 구분되어 주어진다. $(1 \leq a_i, b_i \leq M)$

달구가 최악의 경우에도 가장 많은 과목을 수강할 수 있도록 우선순위를 배정했을 때, 최악의 경우에 수강할 수 있는 과목의 개수를 구하라.