#L3135. 「COCI 2019.3」Simfonija

「COCI 2019.3」Simfonija

题目描述
译自 COCI 2018/2019 Contest #6 T4「Simfonija」

给两个长度为 NN 的数列 A,BA,B 以及一个整数 KK,你首先可以将 AA 数列的整体加上一个整数 XX,然后修改其中 KK 个数,请最小化 [ \sum_{i=1}^N \left|A_i - B_i\right| ]

输入格式
第一行两个整数 N,KN, K,表示数列的长度和可修改的次数。
接下来一行输入 NN 个整数,第 ii 个表示 AiA_i
接下来一行输入 NN 个整数,第 ii 个表示 BiB_i

输出格式
输出一行一个整数,表示最优情况下,题目描述中表达式的最小值。

样例 1
输入

3 0
1 2 3
4 5 7

输出

1

样例 2
输入

3 1
1 2 3
4 5 7

输出

0

AA 整体加上 X=3X = 3,然后将 A3A_3 修改为 77

样例 3
输入

4 1
1 2 1 2
5 6 7 8

输出

2

数据范围与提示
对于 40%40\% 的数据,保证 K=0K = 0
对于 100%100\% 的数据,保证 $1\le N\le 10^5, 0\le K \le N, -10^6 \le A_i, B_i \le 10^6$。