Minimum Segment Cost

Input

The first line contains two integers $n$ and $k$ ( $4 \leq n \leq 3000$ 4 \le n \le 3000, $2 \leq k \leq n - 2$ 2 \le k \le n-2).

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1,a_2,\ldots,a_n ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \le a_i \le 10^9).

The third line contains $n$ integers $c_{1}, c_{2}, \dots, c_{n}$ c_1,c_2,\ldots,c_n ( $- 1 0^{9} \leq c_{i} \leq 1 0^{9}$ -10^9 \le c_i \le 10^9).

Print one integer — the minimum possible cost.

Example 1

Loading

In the example:

For $l = 3$ l=3 and $r = 4$ r=4, we have

b = [3, 4, 5, 5, 4, 3] .

b=[3,4,5,5,4,3].

The distances from the positions to the segment $[3, 4]$ are

[2, 1, 0, 0, 1, 2] .

[2,1,0,0,1,2].

Since $b_{l} = b_{3} = 5$ b_l=b_3=5, we get

[b_{l} - d_{1}, b_{l} - d_{2}, \dots, b_{l} - d_{n}] = [3, 4, 5, 5, 4, 3] .

[b_l-d_1,b_l-d_2,\ldots,b_l-d_n] = [3,4,5,5,4,3].

Therefore, the cost of this segment is

i = 1 \sum n ∣ b_{i} - b_{l} + d_{i} ∣ = 0.

\sum_{i=1}^{n}|b_i-b_l+d_i|=0.

Since the cost cannot be negative, the answer is $0$ .