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 翻译）