P2876 [USACO07JAN] Problem Solving G

在较为轻松的日子里，Farmer John 的奶牛们没有任何问题。然而，如今它们却有许多问题，确切地说，它们有 $P$ 个问题，其中 $1 \leq P \leq 300$。它们已经停止提供牛奶，并像其他好公民一样找了常规工作。实际上，在一个正常的月份里，它们可以赚取 $M$ 的钱，其中 $1 \leq M \leq 1000$。 然而，它们的问题非常复杂，以至于必须雇佣顾问来解决。顾问不是免费的，但他们很有能力：顾问可以在一个月内解决任何一个问题。每个顾问要求两次付款：一次是在开始解决问题的月份开始时支付的预付款（$1 \leq \text{payment} \leq M$），另一次是在问题解决后的下个月开始时支付的尾款（$1 \leq \text{payment} \leq M$）。因此，每个月奶牛们可以用上个月赚的钱来支付顾问的费用。奶牛们是挥霍无度的，它们无法从一个月到下个月存钱；未使用的钱会浪费在牛糖果上。 由于要解决的问题之间存在依赖关系，它们必须大部分按顺序解决。例如，问题 3 必须在问题 4 之前解决，或者与问题 4 在同一个月解决。 确定解决所有奶牛问题并支付解决费用所需的月份数。

第 1 行：两个用空格分隔的整数：$M$ 和 $P$。 第 2 行到第 $P+1$ 行：第 $i+1$ 行描述问题 $i$，包含两个用空格分隔的整数：$B_i$ 和 $A_i$。$B_i$ 是在问题解决之前支付给顾问的费用；$A_i$ 是在问题解决之后支付给顾问的费用。

第 1 行：解决并支付所有奶牛问题所需的月份数。

| 月份 | 当月收入 | 当月解决的问题 | 当月支付的预付款 | 当月支付的尾款 | 浪费金额 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $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$ | （由 ChatGPT 4o 翻译）