Description

You are given two arrays $A$ and $B$, each containing $N$ elements. Add an integer $X$ to every element in array $A$, and then modify at most $K$ elements, so that the following expression is minimized:

Input Format

The first line contains integers $N, K$.

The second line contains $N$ integers $A_i$.

The third line contains $N$ integers $B_i$.

Output Format

Output the minimum value of the expression after the operations.

3 0
1 2 3
4 5 7

1

3 1
1 2 3
4 5 7

0

4 1
1 2 1 2
5 6 7 8

2

Hint

Explanation for Sample 2

When choosing $X = 3$ and changing the last number in array $A$ to $7$, the two arrays $A$ and $B$ become exactly the same, so the value of the expression is $0$.

Constraints

For $40\%$ of the testdata, $K = 0$.

For $100\%$ of the testdata, $1 \le N \le 10^5$, $0 \le K \le N$, $-10^6 \le A_i, B_i \le 10^6$.

Note

The score for this problem follows the original COCI settings, with a full score of $110$.

Translated from COCI2018-2019 CONTEST #6 T4 Simfonija.

Translated by ChatGPT 5