#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// (a, b) -> ax+b
long long at(const pair<long long, long long>& line, long long x) {
    return line.first * x + line.second;
}

const long long INF = 8e18;
const pair<long long, long long> NONE(-1, -1);
vector<long long> points;

struct LiChao {
    pair<long long, long long> tree[(1 << 20) + 228];
    void build(int v, int left, int right) {
        tree[v] = NONE;
        if (left + 1 == right)
            return;
        int mid = (left + right) / 2;
        build(2 * v + 1, left, mid);
        build(2 * v + 2, mid, right);
    }
    void add_line(int v, int left, int right, int x, int y, pair<long long, long long> line) {
        if (y <= left || right <= x)
            return;
        int mid = (left + right) / 2;
        if (x <= left && right <= y) {
            if (tree[v] == NONE) {
                tree[v] = line;
                return;
            }
            if (at(tree[v], points[mid]) >= at(line, points[mid])) {
                swap(tree[v], line);
            }
            if (left + 1 == right)
                return;
            bool better_l = at(tree[v], points[left]) > at(line, points[left]);
            bool better_r = at(tree[v], points[right - 1]) > at(line, points[right - 1]);
            if (better_l)
                add_line(2 * v + 1, left, mid, x, y, line);
            if (better_r)
                add_line(2 * v + 2, mid, right, x, y, line);
        } else {
            add_line(2 * v + 1, left, mid, x, y, line);
            add_line(2 * v + 2, mid, right, x, y, line);
        }
    }
    long long get(int v, int left, int right, int i) {
        long long cur = tree[v] == NONE ? INF : at(tree[v], points[i]);
        if (left + 1 == right)
            return cur;
        int mid = (left + right) / 2;
        if (i < mid)
            return min(cur, get(2 * v + 1, left, mid, i));
        return min(cur, get(2 * v + 2, mid, right, i));
    }
};

const int K = 25;
LiChao trees[2 * K];

void solve() {
    int n, k;
    cin >> n >> k;
    k = min(k, K - 1);
    vector<pair<long long, long long>> A(n);
    for (int i = 0; i < n; ++i)
        //A[i].first = rand() % (1000000000) + 1;
        cin >> A[i].first;
    for (int i = 0; i < n; ++i)
        //A[i].second = rand() % (1000000000) + 1;
        cin >> A[i].second;
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&A](int a, int b) {
        return A[a] < A[b];
    });
    int real_st = 0;
    int real_end = 0;
    while (order[real_st] != 0)
        ++real_st;
    while (order[real_end] != n - 1)
        ++real_end;

    vector<long long> x(n);
    vector<long long> s(n);
    for (int i = 0; i < n; ++i) {
        x[i] = A[order[i]].first;
        s[i] = A[order[i]].second;
    }

    // 2 * i + 0 - i swaps, to left
    // 2 * i + 1 - i swaps, to right

    for (int j = 0; j < 2 * (k + 1); ++j)
        trees[j].build(0, 0, n);
    points = x;

    sort(order.begin(), order.end(), [&](int a, int b) {
        return s[a] > s[b];
    });
    long long ans = INF;
    for (int i : order) {
        if (i == real_st) {
            trees[0].add_line(0, 0, n, 0, i + 1, make_pair(-s[i], s[i] * x[i]));
            trees[1].add_line(0, 0, n, i, n, make_pair(s[i], -s[i] * x[i]));
        } else {
            for (int j = 0; j < 2 * (k + 1); j += 2) {
                long long t = trees[j].get(0, 0, n, i);
                if (t == INF)
                    break;
                // left
                trees[j].add_line(0, 0, n, 0, i + 1, make_pair(-s[i], t + s[i] * x[i]));
                // switch side
                if (j < 2 * k)
                    trees[(j ^ 1) + 2].add_line(0, 0, n, i, n, make_pair(s[i], t - s[i] * x[i]));
            }
            for (int j = 1; j < 2 * (k + 1); j += 2) {
                long long t = trees[j].get(0, 0, n, i);
                if (t == INF)
                    break;
                // right
                trees[j].add_line(0, 0, n, i, n, make_pair(s[i], t - s[i] * x[i]));
                // switch side
                if (j < 2 * k)
                    trees[(j ^ 1) + 2].add_line(0, 0, n, 0, i + 1, make_pair(-s[i], t + s[i] * x[i]));
            }
        }
    }
    for (int j = 0; j < 2 * (k + 1); ++j)
        ans = min(ans, trees[j].get(0, 0, n, real_end));
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}