#P1166. Game of Swapping Numbers

    ID: 202 Type: Default 1000ms 256MiB Tried: 1 Accepted: 1 Difficulty: 10 Uploaded By: Tags>其他贪心多校训练牛客多校结论

Game of Swapping Numbers

Background

2021nowcoder多校day1 数据手造,如果想品尝原汁原味的数据,请在nowcoder购买

Description

Given two arrays A, B with length N, you should perform exactly K operations in array A.

For each operation, choose 2 elements Ai,Aj(1i<jN)A_i, A_j(1 \leq i < j \leq N)and swap the positions of AiA_i and AjA_j.

Please maximize i=1nAiBi\sum_{i = 1}^{n}|A_i - B_i|.

Format

Input

The first line of input contains two integers $N, K(2 \leq N \leq 5 \times 10^5, 0 \leq K \leq 10^8)$, describing the length of A, B and number of operations.

The second line contains N integers A1,...,AN(108Ai108)A_1,...,A_N(-10^8 \leq A_i \leq 10^8).

The third line contains N integers B1,...,BN(108Bi108)B_1,...,B_N(-10^8 \leq B_i \leq 10^8).

Output

Output one integer, the maximum answer

Samples

3 2
1 2 3
3 2 1
4
3 2
1 2 3
1 2 3
4
3 1
1 2 3
3 2 1
4

Limitation

1s, 1024KiB for each test case.