1914C.cpp

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

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

    int t;
    cin >> t;

    while (t--)
    {
        int n, k;
        cin >> n >> k;
        int val = min(n, k);
        int max_val = 0;
        vector<int> a(n), b(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i < val)
                max_val += a[i];
        }

        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }

        vector<int> prefix_max(val);
        prefix_max[0] = b[0];
        for (int i = 1; i < val; i++) {
            prefix_max[i] = max(prefix_max[i - 1], b[i]);
        }

        int current_sum = max_val;

        for (int replaced = 0; replaced < val; replaced++)
        {
            if (replaced != 0)
                current_sum -= a[val - replaced];

            int temp = current_sum;
            int max_b = prefix_max[val - replaced - 1];
            current_sum += max_b * (replaced + max(0, k - n));
            max_val = max(max_val, current_sum);
            current_sum = temp;
        }

        cout << max_val << '\n';
    }

    return 0;
}