Tian Ji — The Horse Racing

Time limit1sMemory limit128 MB

Summary

Given two sets of n horse speeds, pair them one to one to maximize Tian Ji's score where a win counts 200, a loss counts -200, and a tie counts 0.

Level: Medium6 of 10
Topics: Greedy, Two pointers, Sorting
Solved: No attempts yet

Problem

Here is a famous story from Chinese history.

About 2300 years ago, General Tian Ji, a high official of the state of Qi, loved to bet on horse races against the king. Both Tian Ji and the king owned three horses, one in each class: regular, plus, and super. A match consists of three rounds, and each horse must be used in exactly one round. The winner of a round takes two hundred silver dollars from the loser.

Because the king's horse in every class was faster than Tian Ji's, the king won all three rounds every time and took six hundred silver dollars from Tian Ji.

Tian Ji was unhappy about this until he met Sun Bin, one of the most famous strategists in Chinese history, who taught him a simple trick. Tian Ji raced his regular horse against the king's super horse, conceding that round on purpose; then his plus horse beat the king's regular horse, and his super horse beat the king's plus horse. With this trick Tian Ji came home two hundred silver dollars richer.

This problem generalizes the story. Tian Ji and the king each have $n$ horses, and every horse has a given speed. A match consists of $n$ rounds; each side places exactly one of its horses in each round. In a round the faster horse wins and the winner takes two hundred silver dollars from the loser; if the two horses have equal speed the round is a draw and no money changes hands.

Assuming Tian Ji arranges his horses in the most favorable way, output the maximum net amount of money he can end up with — the silver he wins minus the silver he loses. This value may be negative.

Input

The input consists of several test cases, at most 50 of them. The first line of each case contains a positive integer $n$ ( $n \le 1000$ ), the number of horses on each side. The second line contains the speeds of Tian Ji's $n$ horses, and the third line contains the speeds of the king's $n$ horses, all separated by spaces. A line containing a single $0$ follows the last case and terminates the input.

Output

For each test case, output on its own line the maximum net amount of silver dollars Tian Ji can obtain.

Examples3

Example 1

Input

Expected output

200
0
0

Example 2
Input
```
1
5
3
0
```
Expected output
```
200
```
Example 3
Input
```
1
3
5
0
```
Expected output
```
-200
```