311312: CF1969D. Shop Game

D. Shop Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice and Bob are playing a game in the shop. There are $n$ items in the shop; each item has two parameters: $a_i$ (item price for Alice) and $b_i$ (item price for Bob).

Alice wants to choose a subset (possibly empty) of items and buy them. After that, Bob does the following:

• if Alice bought less than $k$ items, Bob can take all of them for free;
• otherwise, he will take $k$ items for free that Alice bought (Bob chooses which $k$ items it will be), and for the rest of the chosen items, Bob will buy them from Alice and pay $b_i$ for the $i$-th item.

Alice's profit is equal to $\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j$, where $S$ is the set of items Bob buys from Alice, and $T$ is the set of items Alice buys from the shop. In other words, Alice's profit is the difference between the amount Bob pays her and the amount she spends buying the items.

Alice wants to maximize her profit, Bob wants to minimize Alice's profit. Your task is to calculate Alice's profit if both Alice and Bob act optimally.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $0 \le k \le n$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$).

Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — Alice's profit if both Alice and Bob act optimally.

ExampleInput

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

Output

1
1
0
7

Note

In the first test case, Alice should buy the $2$-nd item and sell it to Bob, so her profit is $2 - 1 = 1$.

In the second test case, Alice should buy the $1$-st, the $2$-nd and the $3$-rd item; then Bob takes the $1$-st item for free and pays for the $2$-nd and the $3$-rd item. Alice's profit is $(3+2) - (1+2+1) = 1$. Bob could take $2$-nd item for free instead; this does not change Alice's profit. Bob won't take the $3$-rd item for free, since this would lead to a profit of $2$.

题目大意：
Alice和Bob在商店里玩游戏。商店里有n件商品，每件商品有两个参数：a_i（Alice购买商品的价格）和b_i（Bob购买商品的价格）。

Alice想选择一个商品子集（可能为空）并购买它们。之后，Bob会做以下事情：
- 如果Alice购买的商品少于k件，Bob可以免费拿走所有商品；
- 否则，他会免费拿走k件Alice购买的商品（Bob选择哪k件商品），对于剩下的商品，Bob会从Alice那里购买并支付b_i的价格。

Alice的利润是 \(\sum_{i \in S} b_i - \sum_{j \in T} a_j\)，其中S是Bob从Alice那里购买的商品集合，T是Alice从商店购买的商品集合。换句话说，Alice的利润是Bob支付给她的金额和她购买商品花费的金额之差。

Alice想最大化她的利润，Bob想最小化Alice的利润。你的任务是计算如果Alice和Bob都采取最优策略，Alice的利润是多少。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含两个整数n和k（1≤n≤2×10^5；0≤k≤n）。
第二行包含n个整数\(a_1, a_2, \ldots, a_n\)（1≤a_i≤10^9）。
第三行包含n个整数\(b_1, b_2, \ldots, b_n\)（1≤b_i≤10^9）。
输入数据的附加限制：所有测试用例的n之和不超过2×10^5。

输出：
对于每个测试用例，打印一个整数——如果Alice和Bob都采取最优策略，Alice的利润是多少。题目大意： Alice和Bob在商店里玩游戏。商店里有n件商品，每件商品有两个参数：a_i（Alice购买商品的价格）和b_i（Bob购买商品的价格）。 Alice想选择一个商品子集（可能为空）并购买它们。之后，Bob会做以下事情： - 如果Alice购买的商品少于k件，Bob可以免费拿走所有商品； - 否则，他会免费拿走k件Alice购买的商品（Bob选择哪k件商品），对于剩下的商品，Bob会从Alice那里购买并支付b_i的价格。 Alice的利润是 \(\sum_{i \in S} b_i - \sum_{j \in T} a_j\)，其中S是Bob从Alice那里购买的商品集合，T是Alice从商店购买的商品集合。换句话说，Alice的利润是Bob支付给她的金额和她购买商品花费的金额之差。 Alice想最大化她的利润，Bob想最小化Alice的利润。你的任务是计算如果Alice和Bob都采取最优策略，Alice的利润是多少。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1≤n≤2×10^5；0≤k≤n）。 第二行包含n个整数\(a_1, a_2, \ldots, a_n\)（1≤a_i≤10^9）。 第三行包含n个整数\(b_1, b_2, \ldots, b_n\)（1≤b_i≤10^9）。 输入数据的附加限制：所有测试用例的n之和不超过2×10^5。 输出： 对于每个测试用例，打印一个整数——如果Alice和Bob都采取最优策略，Alice的利润是多少。