SOLVE

LATER

Strange Game

/

Alice and Bob are very good friends. They keep on playing some strange games. Today Alice came up with a new game, in which each player gets \(N\) cards at the start. Each card has it's value printed on it.

The game proceeds as each player chooses a random card and shows it's value. The player having card with higher value wins. As Alice came up with this game, he wants to ensure his win. So he starts to increase value of some cards using an algorithm. To increase the value of a card by \(1\), the running time of algorithm is \(K\) seconds.

Find the minimum running time of algorithm, ensuring the win of Alice.

**Input**:

First line of input contains an integer \(T\) denoting the number of TestCases.

First line of Each testcase contains two Integers \(N\) and \(K\).

Next two lines of each TestCase contains \(N\) integers, each denoting value of cards of Alice and Bob respectively.

**Output**:

Print a single line for each TestCase, running time of algorithm to ensure the win for Alice.

**Constraints**:

\(1 \leq T \leq 100\)

\(1 \leq N \leq 10^5\)

\(1 \leq K \leq 20\)

\(0 \leq Value\,of\,each\,card \leq 10^6\)

Explanation

There are 3 TestCases.

In 1^{st} TestCase there are 5 cards and the time required to increase the value of a card by one is 3.

Initial values on Alice's cards are \(8, 9, 10, 23, 4\).

If he converts the the above array into \(14, 14, 14, 23, 14.\) Then it's guranteed that he will win with minimum running time of algorithm.

For this conversion the running time of algorithm for:

1^{st }element :- \(6*3 = 18sec\)

2^{nd} element :- \(5*3 = 15 sec\)

3^{rd} element :- \(4*3=12sec\)

4^{th }element :- \(0*3=0sec\)

5^{th} element :- \(10*3=30sec\)

Hence the total running time of algorithm for 1^{st} TestCase is \(18+15+12+0+30 = 75sec\)

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...