13073 - 1.3.1 Mixing Milk 混合牛奶

牛奶包装是一个利润极低的生意，因此控制原料（牛奶）的价格至关重要。请帮助快乐的牛奶制造公司（Merry Milk Makers）以最便宜的方式购买所需数量的牛奶。

该公司每天从若干农民手中购买牛奶，每个农民的牛奶价格可能不同，且每个农民每天只能提供有限数量的牛奶。公司每天需要一定量的牛奶，并且可以从每个农民处购买不超过其最大供应量的任意数量。

给定公司每日的牛奶需求量和每个农民的价格及供应量，请计算满足需求所需的最小总费用。

第一行包含两个整数 N 和 M：

• N（0 ≤ N ≤ 2,000,000）：公司一天所需的牛奶总量（加仑）。
• M（0 ≤ M ≤ 5,000）：可提供牛奶的农民人数。

接下来 M 行，每行包含两个整数 Pi 和 Ai：

• Pi（0 ≤ P_i ≤ 1,000）：第 i 个农民的每加仑牛奶价格。
• Ai（0 ≤ A_i ≤ 2,000,000）：该农民一天最多能出售的牛奶量（加仑）。

数据保证所有农民的牛奶供应总量 ≥ N，即一定可以满足需求。

输出一个整数，表示满足需求所需的最小总费用。

样例说明

• 需求 100 加仑。
• 农民价格及供应量：
  • 价格 3，供应 10
  • 价格 5，供应 20
  • 价格 6，供应 30
  • 价格 8，供应 80
  • 价格 9，供应 40
• 最优购买策略：按价格从低到高购买：
  • 买 10 加仑（价格 3），费用 30
  • 再买 20 加仑（价格 5），费用 100
  • 再买 30 加仑（价格 6），费用 180
  • 还需 100 - 10 - 20 - 30 = 40 加仑，从价格 8 的农民处购买 40 加仑，费用 320
• 总费用 = 30 + 100 + 180 + 320 = 630

数据范围与约定

• 0 ≤ N ≤ 2,000,000
• 0 ≤ M ≤ 5,000
• 0 ≤ Pi ≤ 1,000
• 0 ≤ Ai ≤ 2,000,000

USACO