문제 해결

젖소들에게는 해결해야 할 문제가 $P$개 있다 ($1 \le P \le 300$). 젖소들은 우유 생산을 그만두고 다른 시민들처럼 평범한 직장에 다니며, 평범한 달에는 $M$원 ($1 \le M \le 1000$)을 번다.

하지만 문제들이 너무 복잡해서 젖소들은 컨설턴트를 고용해야만 문제를 해결할 수 있다. 컨설턴트는 유능해서 어떤 문제든 한 달 만에 해결한다. 각 컨설턴트는 두 번의 보수를 요구한다. 하나는 선금으로 그 문제의 해결을 시작하는 달의 초에 지불하고, 다른 하나는 후금으로 그 문제가 해결된 다음 달의 초에 지불한다.

젖소들은 매달, 바로 전달에 번 돈으로만 컨설턴트에게 보수를 지불할 수 있다. 젖소들은 낭비벽이 심해서 돈을 다음 달로 넘기지 못하며, 쓰지 않은 돈은 모두 사탕을 사 먹는 데 써 버린다. 따라서 매달 쓸 수 있는 금액은 정확히 $M$원이고, 첫째 달에는 전달이 없으므로 쓸 수 있는 돈이 없다.

문제들은 서로 의존 관계가 있어 대체로 순서대로 해결해야 한다. 예를 들어 문제 3은 문제 4보다 먼저 해결되거나, 늦어도 문제 4와 같은 달에 해결되어야 한다. 즉, 한 달에 해결하는 문제들은 언제나 번호가 연속된 구간을 이룬다.

모든 문제를 해결하고 컨설턴트에게 보수를 전부 지불하는 데 걸리는 최소 개월 수를 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $M$과 $P$.
• 둘째 줄부터 $P+1$째 줄까지: $i+1$째 줄은 문제 $i$에 대한 두 정수 $B_i$와 $A_i$를 공백으로 구분하여 준다. $B_i$는 문제를 해결하기 전에 지불하는 선금, $A_i$는 문제가 해결된 뒤에 지불하는 후금이며, $1 \le B_i \le M$, $1 \le A_i \le M$이다.

• 첫째 줄: 모든 문제를 해결하고 보수를 전부 지불하는 데 걸리는 최소 개월 수.

아래 표는 예제 입력에 대한 진행 과정을 보여 준다. 매달 쓸 수 있는 돈은 $100$원이고, 첫째 달에는 쓸 수 있는 돈이 없다.

+-------+-------+--------+---------+---------+--------+
|       | 사용   | 해결한  |  선금    |  후금    | 남은   |
| 달    | 가능액 | 문제   |  지불    |  지불    | 돈     |
+-------+-------+--------+---------+---------+--------+
|   1   |   0   |  없음  |    0    |    0    |    0   |
|   2   |  100  |  1, 2  |  40+60  |    0    |    0   |
|   3   |  100  |  3, 4  |  30+30  |  20+20  |    0   |
|   4   |  100  |  없음  |    0    |  50+50  |    0   |
|   5   |  100  |   5    |   40    |    0    |   60   |
|   6   |  100  |  없음  |    0    |   40    |   60   |
+-------+-------+--------+---------+---------+--------+

따라서 모든 문제를 해결하고 보수를 지불하는 데 $6$개월이 걸린다.