C. dota 2

题目描述

Bobo最近学会了玩Dota2。在Dota2的比赛中，为了问题的简化，引入了禁用/选择英雄的机制，并作了如下修改：

假设比赛是在两个队伍之间进行的：A队和B队。每个队伍都有一个包含$n$个英雄的英雄池，其对应的积分分别为$a_1, \cdots,a_n$和$b_1, \cdots, b_n$。在这里，我们假设两个队伍的英雄池中的所有英雄都是不同的。

接着，两个队伍交替进行禁用/选择操作，A队先开始。在一个队伍的回合中，他们可以为自己选择一个英雄，或者禁用对手英雄池中尚未被选择的英雄。

经过2n轮操作后，所有英雄都将被选择或禁用。然后，每个队伍需要从其选择的所有英雄中选择最多$k$个英雄来组成一个战队，而该战队的得分将由其中所有英雄的积分之和计算而得。

设$sA$、$sB$分别为A队和B队组成的战队的得分。A队希望最大化$sA - sB$的值，而B队希望将其最小化。

Bobo想知道，如果两个队伍都采取最优策略，$sA - sB$的最终值应该是多少

输入格式

第一行输入两个整数$n, k$

第二行输入$n$个整数$a_1, a_2, \cdots, a_n$

第三行输入$n$个整数$b_1, b_2, \cdots, b_n$

输出格式

输出一个整数表示答案

样例输入1

2 1
3 6
2 4

样例输出1

2

样例输入2

4 1
1 3 5 7
2 4 6 8

样例输出2

0

数据范围

对于30%的数据，$n \leq 5$

对于60%的数据，$n \leq 1000$

对于100%的数据，$n \leq 10^5, k \leq min(n, 10), a_i, b_i \leq 10^8$