P12951 [GCJ Farewell Round #2] Collecting Pancakes

**Alice** 和 **Bob** 都喜欢吃甜食，他们准备玩一个收集煎饼的游戏。桌上有 $\mathbf{N}$ 叠煎饼排成一列，编号从 1 到 $\mathbf{N}$。第 $i$ 叠煎饼恰好有 $\mathbf{A}_{i}$ 个。**Alice** 和 **Bob** 将轮流选择整叠煎饼来收集。第一回合，**Alice** 必须选择一个编号在 $[\mathbf{L}_{\mathrm{a}}, \mathbf{R}_{\mathrm{a}}]$ 范围内的煎饼叠并收集它。接着，**Bob** 必须选择一个编号在 $[\mathbf{L}_{\mathrm{b}}, \mathbf{R}_{\mathrm{b}}]$ 范围内且不同于 **Alice** 所选叠的煎饼叠并收集它。 在后续回合中，每个人都必须选择一个未被收集且与之前自己收集过的叠相邻的煎饼叠。也就是说，**Alice** 在非首回合选择第 $i$ 叠时，她必须在此前的某个回合中收集过第 $i-1$ 叠或第 $i+1$ 叠。**Bob** 也遵循同样的规则。如果在某一回合中某位玩家没有合法选择，则该玩家跳过此回合，不收集任何煎饼叠。 游戏在所有煎饼叠都被收集时结束。此时，**Alice** 将获得她收集的所有叠中的煎饼总数，**Bob** 则获得他收集的所有叠中的煎饼总数。 **Alice** 希望自己获得的煎饼尽可能多，而 **Bob** 则希望自己获得的煎饼尽可能多。在双方都采取最优策略的情况下，你能帮 **Alice** 计算出她最多能获得多少煎饼吗？

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个测试用例包含三行。 每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示煎饼叠的数量。 第二行包含 $\mathbf{N}$ 个整数 $\mathbf{A}_{1}, \mathbf{A}_{2}, \ldots, \mathbf{A}_{\mathbf{N}}$，其中 $\mathbf{A}_{i}$ 表示第 $i$ 叠煎饼的数量。 第三行包含 4 个整数 $\mathbf{L}_{\mathrm{a}}, \mathbf{R}_{\mathrm{a}}, \mathbf{L}_{\mathrm{b}}, \mathbf{R}_{\mathrm{b}}$，分别表示 **Alice** 和 **Bob** 首回合可选煎饼叠编号的闭区间范围。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 **Alice** 在双方最优策略下能获得的最大煎饼数量。

**样例解释** 在样例 #1 中，5 叠煎饼的数量分别为 30、50、40、20、10。**Alice** 首回合可选择第 1 或第 2 叠，**Bob** 首回合可选择第 4 或第 5 叠。双方的一种最优策略如下： 1. **Alice** 首回合选择第 2 叠，**Bob** 选择第 4 叠。 2. **Alice** 第二回合选择第 3 叠，**Bob** 选择第 5 叠。 3. **Alice** 第三回合选择第 1 叠，游戏结束。 最终 **Alice** 收集了第 1、2、3 叠，获得 $30 + 50 + 40 = 120$ 个煎饼。 在样例 #2 中，一种最优策略为： 1. **Alice** 首回合选择第 3 叠，**Bob** 选择第 2 叠。 2. **Alice** 第二回合选择第 4 叠，**Bob** 选择第 1 叠。 3. **Alice** 第三回合选择第 5 叠，游戏结束。 **Alice** 共获得 $80 + 10 + 10 = 100$ 个煎饼。 在样例 #3 中，双方首回合可选择任意叠。由于第 1 叠的价值超过其他叠的总和，**Alice** 会优先选择它。接着 **Bob** 只能选择第 2 叠，导致 **Alice** 后续无法操作。最终 **Alice** 获得 90 个煎饼，**Bob** 仅获得 30 个。 **数据范围** - $1 \leq \mathbf{T} \leq 100$。 - 对所有 $i$，$1 \leq \mathbf{A}_{i} \leq 10^{9}$。 - $1 \leq \mathbf{L}_{\mathrm{a}} \leq \mathbf{R}_{\mathrm{a}} \leq \mathbf{N}$。 - $1 \leq \mathbf{L}_{\mathrm{b}} \leq \mathbf{R}_{\mathrm{b}} \leq \mathbf{N}$。 - 保证不存在 $\mathbf{L}_{\mathrm{a}} \leq \mathbf{L}_{\mathrm{b}}=\mathbf{R}_{\mathrm{b}} \leq \mathbf{R}_{\mathrm{a}}$ 的情况（即 **Bob** 首回合总能选择合法叠）。 **测试集 1（4 分，可见判定）** - $2 \leq \mathbf{N} \leq 100$。 **测试集 2（10 分，可见判定）** - $2 \leq \mathbf{N} \leq 10^{5}$。 翻译由 DeepSeek V3 完成