Description

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 计算出她最多能获得多少煎饼吗？

Input Format

输入的第一行给出测试用例的数量 $\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 首回合可选煎饼叠编号的闭区间范围。

Output Format

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

3
5
30 50 40 20 10
1 2 4 5
5
20 20 80 10 10
1 4 2 5
4
90 10 10 10
1 4 1 4

Case #1: 120
Case #2: 100
Case #3: 90

Hint

样例解释

在样例 #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 完成