题目描述

In easier times, Farmer John's cows had no problems. These days, though, they have problems, lots of problems; they have P (1 ≤ P ≤ 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make M (1 ≤ M ≤ 1000) money.

Their problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 ≤ payment ≤ M) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 ≤ payment ≤ M). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy.

Since the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4.

Determine the number of months it takes to solve all of the cows' problems and pay for the solutions.

输入格式

Line 1: Two space-separated integers: M and P.

Lines 2..P+1: Line i+1 describes problem i with two space-separated integers: Bi and Ai. Bi is the payment to the consult BEFORE the problem is solved; Ai is the payment to the consult AFTER the problem is solved.

输出格式

Line 1: The number of months it takes to solve and pay for all the cows' problems.

题目大意

在经济状况较好的时候，FJ 的奶牛没有任何问题。但如今，它们有 $P$（$1 \le P \le 300$）个问题。他们不再提供牛奶，而是像所有其他好公民一样找到了固定的工作。事实上，在一个正常的月份，他们赚了 $M$（$1 \le M \le 1000$）元钱。

然而，他们的问题非常复杂，他们必须聘请顾问来解决。咨询师不是免费的，但他们很有能力。咨询师可以在一个月内解决任何问题。每个咨询师要求两次付款，一次是在开始解决问题的月初提前支付 $a_i$ 元（$1 \le a_i \le M$），另一次是在问题解决后的月初再支付 $b_i$ 元（$1 \le b_i \le M$），这样奶牛每个月就可以用上个月赚的钱来支付咨询师的费用。

由于所要解决的问题是相互依存的，所以它们必须基本上按顺序解决。例如，问题 $3$ 必须在问题 $4$ 之前解决，或者在问题 $4$ 的同一个月内解决。

确定解决奶牛所有问题所需的月数，并支付解决方案的费用。

注意：奶牛不会存钱，每个月赚到的钱没有用完就会消失。

100 5
40 20
60 20
30 50
30 50
40 40

6

提示