#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct CHT {
    int pointer=0;
    vector<long long> K, B;
    void clear() {
        pointer = 0;
        K.clear();
        B.clear();
    }
    bool bad(int l1, int l2, int l3) {
        return (B[l3] - B[l1]) * (K[l1] - K[l2]) < (B[l2] - B[l1]) * (K[l1] - K[l3]);
    }
    void add(long long k, long long b) {
        if (!K.empty() && K.back() == k) return;
        K.push_back(k);
        B.push_back(b);
        while (K.size() >= 3 && bad(K.size() - 3, K.size() - 2, K.size() - 1)) {
            K.erase(K.end()-2);
            B.erase(B.end()-2);
        }
    }
    ll getmin(long long x) {
        int lef = 0, rig = K.size() - 1;
        while (lef < rig) {
            int mid = (lef + rig) / 2;
            if (K[mid] * x + B[mid] > K[mid + 1] * x + B[mid + 1]) {
                lef = mid + 1;
            } else {
                rig = mid;
            }
        }
        return K[lef] * x + B[lef];
//        while (pointer < K.size()-1 && K[pointer+1] * x + B[pointer+1] < K[pointer] * x + B[pointer]) pointer++;
//        return K[pointer] * x + B[pointer];
    }
};

const ll inf = 1e18 + 10;
const int K = 50;
const int N = 3e5 + 10;
int x_init[N], s_init[N];
int x[N], s[N];
tuple<int, int, int> c3[N];
ll dp_lef[2][N], dp_rig[2][N];

ll solve(int n, int k) {
    for (int i = 1; i <= n; i++) {
        c3[i] = {x[i], s[i], i};
    }
    sort(c3 + 1, c3 + n + 1);
    int src, trg;
    for (int i = 1; i <= n; i++) {
        auto [cur_x, cur_s, cur_i] = c3[i];
        x[i] = cur_x;
        s[i] = cur_s;
        if (cur_i == 1) {
            src = i;
        }
        if (cur_i == n) {
            trg = i;
        }
    }
    ll ans = inf;
    {
        stack<int> st;
        for (int i = 1; i <= n; i++) {
            while (!st.empty() && s[i] <= s[st.top()]) {
                st.pop();
            }
            dp_lef[0][i] = inf;
            if (i >= trg) {
                dp_lef[0][i] = min(dp_lef[0][i], 1ll * s[i] * (x[i] - x[trg]));
                if (!st.empty()) {
                    int j = st.top();
                    dp_lef[0][i] = min(dp_lef[0][i], 1ll * s[i] * (x[i] - x[j]) + dp_lef[0][j]);
                }
            }
            st.push(i);
        }
        while (!st.empty()) {
            st.pop();
        }
        for (int i = n; i >= 1; i--) {
            while (!st.empty() && s[i] <= s[st.top()]) {
                st.pop();
            }
            dp_rig[0][i] = inf;
            if (i <= trg) {
                dp_rig[0][i] = min(dp_rig[0][i], 1ll * s[i] * (x[trg] - x[i]));
                if (!st.empty()) {
                    int j = st.top();
                    dp_rig[0][i] = min(dp_rig[0][i], 1ll * s[i] * (x[j] - x[i]) + dp_rig[0][j]);
                }
            }
            st.push(i);
        }
        ans = min({ans, dp_lef[0][src], dp_rig[0][src]});
    }
    for (int iter = 1; iter <= min(k, K); iter++) {
        for (int i = 1; i <= n; i++) {
            dp_lef[1][i] = dp_rig[1][i] = inf;
        }

        stack<int> st;
        CHT cht;
        for (int i = 1; i <= n; i++) {
            while (!st.empty() && s[i] <= s[st.top()]) {
                st.pop();
            }
            dp_lef[1][i] = inf;
            if (!st.empty()) {
                int j = st.top();
                dp_lef[1][i] = min(dp_lef[1][i], 1ll * s[i] * (x[i] - x[j]) + dp_lef[1][j]);
                if (i >= 2) {
                    dp_lef[1][i] = min(dp_lef[1][i], 1ll * s[i] * x[i] + cht.getmin(s[i]));
                }
            }
            st.push(i);
            cht.add(-x[i], dp_rig[0][i]);
        }
        while (!st.empty()) {
            st.pop();
        }
        cht.clear();
        for (int i = n; i >= 1; i--) {
            while (!st.empty() && s[i] <= s[st.top()]) {
                st.pop();
            }
            dp_rig[1][i] = inf;
            if (!st.empty()) {
                int j = st.top();
                dp_rig[1][i] = min(dp_rig[1][i], 1ll * s[i] * (x[j] - x[i]) + dp_rig[1][j]);
                if (i <= n - 1) {
                    dp_rig[1][i] = min(dp_rig[1][i], -1ll * s[i] * x[i] + cht.getmin(s[i]));
                }
            }
            st.push(i);
            cht.add(x[i], dp_lef[0][i]);
        }

        swap(dp_lef[0], dp_lef[1]);
        swap(dp_rig[0], dp_rig[1]);

        ans = min({ans, dp_lef[0][src], dp_rig[0][src]});
    }
    return ans;
}

bool getbit(int mask, int bit) {
    return mask & (1 << bit);
}

ll slow(int n, int k) {
    ll res = inf;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (getbit(mask, 0) && getbit(mask, n - 1)) {
            vector<int> ord;
            ord.push_back(1);
            for (int i = 2; i <= n - 1; i++) {
                if (getbit(mask, i - 1)) {
                    ord.push_back(i);
                }
            }
            ord.push_back(n);
            do {
                ll cur = 0;
                int cnt_rot = 0;
                for (int i = 1; i < ord.size(); i++) {
                    cur += 1ll * s[ord[i - 1]] * abs(x[ord[i]] - x[ord[i - 1]]);
                }
                for (int i = 1; i + 1 < ord.size(); i++) {
                    if (1ll * (x[ord[i]] - x[ord[i - 1]]) * (x[ord[i + 1]] - x[ord[i]]) <= 0) {
                        cnt_rot++;
                    }
                }
                if (cnt_rot <= k) {
                    res = min(res, cur);
                }
            } while (next_permutation(ord.begin() + 1, ord.end() - 1));
        }
    }
    return res;
}

void stress() {
    mt19937 rnd;
    while (true) {
        int n = rnd() % 8 + 1;
        int k = rnd() % (n + 1);
        set<int> used_x;
        for (int i = 1; i <= n; i++) {
            do {
                x[i] = rnd() % 100 + 1;
            } while (used_x.count(x[i]));
            s[i] = rnd() % 100 + 1;
            used_x.insert(x[i]);
        }
        for (int i = 1; i <= n; i++) {
            x_init[i] = x[i];
            s_init[i] = s[i];
        }
        ll ans = solve(n, k);
        for (int i = 1; i <= n; i++) {
            x[i] = x_init[i];
            s[i] = s_init[i];
        }
        ll res = slow(n, k);
        if (ans == res) {
            cout << "OK" << endl;
        } else {
            cout << "WA\n";
            cout << "1\n";
            cout << n << " " << k << "\n";
            for (int i = 1; i <= n; i++) {
                cout << x[i] << " ";
            }
            cout << "\n";
            for (int i = 1; i <= n; i++) {
                cout << s[i] << " ";
            }
            cout << "\n\n";
            cout << ans << " " << res << "\n";
            break;
        }
    }
    exit(0);
}

void gen_big() {
    mt19937 rnd;
    int n = 3e5;
    int k = n;
    set<int> used_x;
    for (int i = 1; i <= n; i++) {
        do {
            x[i] = rnd() % 100000000 + 1;
        } while (used_x.count(x[i]));
        s[i] = rnd() % 100000000 + 1;
        used_x.insert(x[i]);
    }
    cout << solve(n, k) << "\n";
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    // stress();
    // gen_big();

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> x[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> s[i];
        }
        cout << solve(n, k) << "\n";
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}