D. Игра в магазине
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру в магазине. В магазине есть $$$n$$$ предметов; каждый предмет имеет два параметра: $$$a_i$$$ (цена предмета для Алисы) и $$$b_i$$$ (цена предмета для Боба).

Алиса хочет выбрать подмножество (возможно, пустое) предметов и купить их. После этого Боб делает следующее:

  • если Алиса купила меньше $$$k$$$ предметов, Боб может взять их все бесплатно;
  • в противном случае, он возьмет $$$k$$$ предметов, купленные Алисой, бесплатно (Боб сам выбирает, какие $$$k$$$ предметов это будут), а остальные выбранные предметы Боб купит у Алисы и заплатит $$$b_i$$$ за $$$i$$$-й предмет.

Прибыль Алисы равна $$$\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j$$$, где $$$S$$$ — множество предметов, которые Боб покупает у нее, а $$$T$$$ — множество предметов, которые она покупает в магазине. Другими словами, прибыль Алисы — это разность между тем, сколько Боб платит ей, и тем, сколько она платит за покупку предметов.

Алиса хочет максимизировать свою прибыль, Боб хочет минимизировать прибыль Алисы. Ваша задача — посчитать прибыль Алисы, если и Алиса, и Боб действуют оптимально.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le n$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — прибыль Алисы, если и Алиса, и Боб действуют оптимально.

Пример
Входные данные
4
2 0
2 1
1 2
4 1
1 2 1 4
3 3 2 3
4 2
2 1 1 1
4 2 3 2
6 2
1 3 4 9 1 3
7 6 8 10 6 8
Выходные данные
1
1
0
7
Примечание

В первом наборе входных данных Алисе следует купить $$$2$$$-й предмет и продать его Бобу, тогда ее прибыль составит $$$2 - 1 = 1$$$.

Во втором наборе входных данных Алисе следует купить предметы $$$1$$$, $$$2$$$ и $$$3$$$; затем Боб берет $$$1$$$-й предмет бесплатно и платит за $$$2$$$-й и $$$3$$$-й предметы. Прибыль Алисы составит $$$(3+2) - (1+2+1) = 1$$$. Боб мог бы взять $$$2$$$-й предмет бесплатно; это не изменит прибыль Алисы. Боб не будет брать $$$3$$$-й предмет бесплатно, так как тогда прибыль Алисы будет равна $$$2$$$.