Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

GPU-Business

By shefin · Limits 1s, 512 MB

You are a businessman who is fond of Vinia GPU. You buy Vinia GPUs from Byteland and sell them to Bitland. There are nn GPU shops in Byteland and mm GPU shops in Bitland. For some reason, the shop owners have put a restriction on you. From a shop in Byteland, you can buy at most 11 GPU. Similarly, you can sell at most 11 GPU to a shop in Bitland. The shop owners also decide the price of the GPU themselves.

You will be given the price of the Vinia GPU in the shops. You have to tell the maximum profit you can make. You can choose not to buy any GPU at all.

Input

The input starts with an integer T(1T1000)T(1\leq T\leq 1000), the number of test cases.

In each test case, the first line contains two space-separated integers n(1n105)n(1\leq n\leq 10^5) and m(1m105)m(1\leq m\leq 10^5), the number of shops in Byteland and Bitland respectively.

The next line contains nn space-separated integers. The ithi^{th} integer represents the price of the Vinia GPU in the ithi^{th} shop in Byteland.
The third line contains mm space-separated integers. The ithi^{th} integer represents the price of the Vinia GPU in the ithi^{th} shop in Bitland.
All the prices will be in [1,109][1, 10^9] range.

The sum of nn over all test cases and the sum of mm over all test cases will not exceed 5×1055\times10^5.

Output

For each test case, print the maximum profit in a line.

Sample

InputOutput
2
3 4
10 70 20
50 60 1 5
3 1
10 70 20
50
80
40

In the first test case, you can buy two GPUs from shop 11 and shop 33 in Byteland and sell them to shop 11 and shop 22 in Bitland.


    Discussion

    Statistics


    89% Solution Ratio

    Siddik_53rdEarliest, 1w ago

    Shan_1603109Fastest, 0.1s

    Asif_AlimLightest, 918 kB

    FrdhsnShortest, 468B

    Submit

    Login to submit

    Editorial

    Let’s say we’ve bought and sold kkk GPUs. Then we can write our profit = (s1+s2+…+sk)−(b1+b2+…+bk)(s...

    Toph uses cookies. By continuing you agree to our Cookie Policy.