Minimizing Absolute Differences with Array Modification

You are given two arrays A and B, each containing N elements. You are allowed to perform the following two operations:

1. Add an integer X (the same for all elements) to every element of array A.
2. Modify (i.e. change arbitrarily) the value of at most K elements of array A after the addition.

Your goal is to choose an integer X and decide which at most K elements to modify so that the following expression is minimized:

$$\sum_{i=1}^N \left| (A_i + X) - B_i \right|$$

For any modified element you can effectively set Ai+X equal to Bi (thus contributing 0 to the sum). Note that you can modify at most K elements, hence at least N-K elements will remain unmodified. For the unmodified elements the cost is |Ai+X - Bi|.

It can be shown that an optimal strategy is to choose a subset S of indices of size exactly N-K (representing the elements you do not modify) and choose X to minimize the cost:

$$\min_{X \in \mathbb{Z}} \sum_{i \in S} \left| (A_i+X) - B_i \right| $$

By defining d_i = B_i - A_i, the cost for a fixed subset becomes

$$\min_{X \in \mathbb{Z}} \sum_{i \in S} |X - d_i|$$

It is known that the sum of absolute differences is minimized when X is chosen as a median of the values {d_i : i \in S}. An optimal choice of the subset S (if modification is allowed on at most K elements) is to take a contiguous block of N-K elements after sorting the array d, because this minimizes the range and hence the sum of absolute differences.

If K \ge N, you can modify all elements, so the answer is 0.

inputFormat

The first line contains two integers N and K (1 ≤ N ≤ 10^5, 0 ≤ K ≤ N), representing the number of elements in the arrays and the maximum number of modifications allowed, respectively.

The second line contains N integers representing the array A.

The third line contains N integers representing the array B.

outputFormat

Output a single integer, the minimum possible value of the following expression after applying the operations optimally:

$$\sum_{i=1}^N |(A_i+X)-B_i|.$$</p> ## sample

5 1
1 3 5 7 9
2 4 6 8 10

0

$$