Shop Game
Contest: Educational Codeforces Round 165 (Rated for Div. 2)
Difficulty rating: 1900
Tags: data structures, greedy, math, sortings

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 format:
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 format:
For each test case, print a single integer — Alice's profit if both Alice and Bob act optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
1
1
0
7

Editorial:
Let's sort the array in descending order based on the array $$$b$$$. For a fixed set of Alice's items, Bob will take the first $$$k$$$ of them for free (because they are the most expensive) and pay for the rest.
Now we can iterate over the first item that Bob will pay (denote it as $$$i$$$). Alice has to buy the cheapest $$$k$$$ items among $$$1, 2, \dots, i-1$$$ (denote the sum of these values as $$$f$$$), because Bob can take them for free. Bob has to pay for each of the items among $$$i, i+1, \dots, n$$$ that Alice will buy. So Alice will buy all the items with $$$b_i - a_i > 0$$$ (denote the sum of these values as $$$p$$$). Then the Alice's profit is $$$p - f$$$.
Thus, we got a solution that works in $$$O(n^2)$$$. In order to speed up this solution, we have to calculate the values $$$f$$$ and $$$p$$$ faster than $$$O(n)$$$. We can do it as follows: while iterating over the value of $$$i$$$, let's store "free" items in the ordered set, and when the size of this set becomes larger than $$$k$$$, remove the most expensive element from it; and the value of $$$p$$$ can be calculated using prefix sums (over the values $$$\max(0, b_i - a_i)$$$) or maintaining a variable (and update it when moving to the next value of $$$i$$$).