Codeforces Round 920 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

greedy

sortings

two pointers

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Very Different Array

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPetya has an array $$$a_i$$$ of $$$n$$$ integers. His brother Vasya became envious and decided to make his own array of $$$n$$$ integers.

To do this, he found $$$m$$$ integers $$$b_i$$$ ($$$m\ge n$$$), and now he wants to choose some $$$n$$$ integers of them and arrange them in a certain order to obtain an array $$$c_i$$$ of length $$$n$$$.

To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $$$D = \sum_{i=1}^{n} |a_i - c_i|$$$ to be as large as possible.

Help Vasya find the maximum difference $$$D$$$ he can obtain.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le m\le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le 10^9$$$). The third line of each test case contains $$$m$$$ integers $$$b_i$$$ ($$$1\le b_i\le 10^9$$$).

It is guaranteed that in a test, the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum total difference $$$D$$$ that can be obtained.

Example

Input

94 66 1 2 43 5 1 7 2 33 41 1 11 1 1 15 51 2 3 4 51 2 3 4 52 65 88 7 5 8 2 102 24 19 64 68 10 6 43 10 6 1 8 93 56 5 21 7 9 7 25 59 10 6 3 75 9 2 3 91 632 7 10 1 1 5

Output

16 0 12 11 10 23 15 25 7

Note

In the first example, Vasya can, for example, create the array $$$(1, 5, 7, 2)$$$. Then the total difference will be $$$D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16$$$.

In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $$$(1, 1, 1)$$$, for which the difference $$$D = 0$$$.

In the third example, Vasya can, for example, create the array $$$(5, 4, 3, 2, 1)$$$. Then the total difference will be $$$D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 15:44:34 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|