410605: GYM104065 A Ban or Pick, What's the Trick

Bobo has recently learned how to play Dota2. In Dota2 competitions, the mechanism of banning/picking heroes is introduced, modified and simplified as follows for the sake of the problem:

Suppose a game is played between two teams: Team A and Team B. Each team has a hero pool of $$$n$$$ heroes with positive utility scores $$$a_1,\dots,a_n$$$ and $$$b_1,\dots,b_n$$$, respectively. Here we assume all heroes in two teams' hero pool are distinct.

The two teams then perform ban/pick operations alternately, with Team A going first. In one team's turn, it can either pick a hero for itself, or ban an unselected hero from the opponent's hero pool.

After $$$2n$$$ turns, all heroes are either picked or banned. Each team then needs to choose at most $$$k$$$ heroes from all heroes it picked to form a warband and the score for the warband is calculated as the sum of utility scores over all heroes in it.

Let $$$s_A, s_B$$$ be the score of the warband formed by Team A and Team B, respectively. Team A wants to maximize the value of $$$s_A-s_B$$$ while Team B wants to minimize it.

Bobo wants to know, what should be the final value of $$$s_A-s_B$$$, if both teams act optimally? He's not really good at calculating this, so he turned to you for help.

An example of banning/picking heroes in Dota2. Source: TI10 True Sight

The first line contains two integers $$$n,k(1\leq n\leq 10^5,1\leq k \leq 10)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\leq a_i\leq 10^8)$$$, denoting the utility score of heroes for Team A.

The third line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(1\leq b_i\leq 10^8)$$$, denoting the utility score of heroes for Team B.

Output an integer in one line, denoting the answer.

2 1
3 6
2 4

2

4 1
1 3 5 7
2 4 6 8

0

4 2
4 6 7 9
2 5 8 10

3