最大配对
测试数据来自 system/1662
背景
Orz5-1 match
描述
给出2个序列A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]},从A、B中各选出k个元素进行一一配对(可以不按照原来在序列中的顺序),并使得所有配对元素差的绝对值之和最大。
例如各选出了a[p[1]],a[p[2]],……,a[p[k]]与b[q[1]],b[q[2]],……,b[q[k]],其中p序列中的元素两两不相同,q序列中的元素两两不相同,那么答案为|a[p[1]]-b[q[1]]|+|a[p[2]]-b[q[2]]|+……+|a[p[k]]-b[q[k]]|,现在任务也就是最大化这个答案。
格式
输入格式
输入的第1行为2个正整数n,k,表示了序列的长度和各要选出元素的个数。
第2行包含n个正整数,描述了A序列。
第3行包含n个正整数,描述了B序列。
输出格式
输出仅包括一个非负整数,为最大的结果。
注意:答案可能超过2^31-1,请使用int64或者long long(若使用printf输出请用“%I64d”)类型储存结果。
样例1
样例输入1
4 2
2 5 6 3
1 4 6 7
样例输出1
10
限制
对于10%的数据,有k≤5,n≤10;
对于30%的数据,有n≤100;
对于50%的数据,有n≤1000;
对于100%的数据,有k≤n≤100000;a[i],b[i]≤1000000。
时限1s。
提示
配对(2,7)、(6,1)结果为|2-7|+|6-1|=10。