注意，你的最终位置取决于你向左移动的次数。假设恰好有 $t$ 次向左移动，那么向右移动的次数就是 $k - t$。不过我们换一种方式来理解：你有 $t$ 对移动（右，左），需要将它们插入到由 $k - 2t$ 次向右移动构成的序列中的某些位置。

容易看出，位置 $1$ 到 $k - 2t + 1$ 都会被访问到。而额外的这些“对”还可以通过访问某个 $i$ 的 $(i+1, i)$ 位置来增加分数，其中 $i$ 的取值范围是 $1$ 到 $k - 2t + 1$。

注意，对于所有这些“对”而言，选择同一个 $i$ 总是最优的。而且这个 $i$ 应该使得 $a_{i+1} + a_i$ 尽可能大。

你可以直接实现这个思路：枚举 $t$，计算从 $1$ 到 $k - 2t + 1$ 的前缀和，以及 $i$ 从 $1$ 到 $k - 2t + 1$ 范围内 $a_{i+1} + a_i$ 的最大值。

这样做每个测试用例的时间复杂度为 $O(z \cdot n)$。

你可以通过预处理前缀和以及最大相邻和来优化到 $O(n)$，或者采用某种巧妙的顺序来枚举 $t$。也可以枚举最终位置，再反推出达到该位置所需的向左移动次数。

总复杂度：每个测试用例 $O(z \cdot n)$ 或 $O(n)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int a[N], pref[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, k, z;
        cin >> n >> k >> z;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            pref[i] = pref[i - 1] + a[i];
        }

        int ans = 0;
        // 枚举向左移动的次数 L
        for (int L = 0; L <= z; ++L) {
            // 总的向右移动次数
            int R = k - L;
            if (R < L) continue; // 至少需要 R >= L 才能有 L 次左移
            int pos = R - L + 1; // 最终停留的位置
            if (pos > n) continue;

            int sum = pref[pos]; // 前缀和

            // 需要在 [1, pos] 范围内找一个相邻对 (i, i+1) 来回 L 次
            // 实际上每次来回会额外加一次 a[i] + a[i+1]，但注意路径分析：
            // 走法：1 -> ... -> i -> i+1 -> i -> i+1 ... 
            // 其中从 i+1 左移到 i 算一次左移，之后必须右移回 i+1 才能继续向前或结束
            // 如果最后一次左移后不右移，那么最终位置是 i。但题目要求总步数固定，
            // 若左移 L 次，总右移 = k - L，净前进 = (k - L) - L = k - 2L，最终位置 = 1 + (k - 2L)。
            // 上面 pos = k - 2L + 1，就是最终位置。这说明最后一次左移后没有右移？检查：
            // 示例 k=4, L=1: pos=4-2+1=3，实际路径右、右、左、右：净前进=3-1=2，最终位置=3，正确。
            // 所以最终位置就是 pos。那么对于 L>0，来回对可以是 pos-1 和 pos 吗？不一定，因为来回必须在路径中。
            // 实际上，最优方案是在某个位置 i 来回 L 次，最终位置 i+1？不对，来回一次会消耗两次步数（左右），净位置不变但总步数 +2。
            // 更准确：路径中，前 (pos-1) 次右移到达 pos，然后进行 L 次“来回”操作，但来回操作包含一次左移和一次右移，
            // 所以总步数 = (pos-1) + 2L = k => pos = k - 2L + 1，与上面一致。
            // 因此，我们可以枚举来回对的位置 i，其中 i 从 1 到 pos-1，来回 L 次后的总得分 = 前缀和到 pos + L * (a[i] + a[i+1])。
            // 并且 L 次来回必须都在同一个 i 进行，否则会前进到更远的位置改变 pos。
            // 所以只需求 [1, pos-1] 范围内最大的 a[i] + a[i+1] 即可。
            if (L > 0) {
                int mx_pair = 0;
                for (int i = 1; i <= pos - 1; ++i) {
                    mx_pair = max(mx_pair, a[i] + a[i + 1]);
                }
                sum += L * mx_pair;
            }
            ans = max(ans, sum);
        }
        cout << ans << '\n';
    }
    return 0;
}