题目 3：爱丽丝能走多远 (GoFarAlice)

题目描述

爱丽丝想要走得尽可能远。她计划开着她的车沿着一条路向 $+x$ 方向前进。

• 耗油量：每单位距离消耗 1 升燃料。
• 燃料容量：油箱容量无限大。
• 初始状态：爱丽丝初始拥有 $M$ 元钱，油箱初始为 0。
• 城市与加油：路线上有 $N$ 个城市。第 $i$ 个城市位于坐标 $x_i$，每升燃料的价格为 $v_i$。爱丽丝只能购买整数单位（升）的燃料。
• 目标：通过计算在哪些城市购买多少燃料，算出爱丽丝能到达的最大距离。

输入格式

• 第一行：两个空格分隔的整数 $M$ ($1 \le M \le 10^9$) 和 $N$ ($1 \le N \le 2 \cdot 10^5$)。
• 接下来的 $N$ 行：每行两个整数 $x_i$ ($0 \le x_i \le 10^9$) 和 $v_i$ ($1 \le v_i \le 10^4$)，代表城市坐标和油价。
• 保证：$x_0 = 0$ 且 $x_i < x_{i+1}$。

输出格式

• 输出一个整数，代表爱丽丝能行驶的最大距离。

使用算法：单调栈 + 贪心算法 (Greedy with Monotonic Stack)

核心逻辑：

1. 贪心策略：如果你在城市 A，你应该只买足够的油走到下一个比 A 油价更便宜的城市 B。因为在 B 买油更划算。
2. 寻找下一个更便宜的城市：
   • 如果能找到下一个更便宜的城市，就购买刚好能到达那里的油。
   • 如果当前城市已经是后面所有城市中最便宜的，或者后面没有城市了，那么就把剩下的钱全部在这里买油，走得越远越好。
3. 单调栈优化：由于我们需要快速找到右侧第一个比当前值小的数，使用单调栈可以将时间复杂度优化到 $O(N)$。