题干：

Two players A and B have a list of nn integers each. They both want to maximize the subtraction between their score and their opponent's score.

In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent's list (assuming his opponent's list is not empty).

Note, that in case there are equal elements in the list only one of them will be affected in the operations above. For example, if there are elements {1,2,2,3}{1,2,2,3} in a list and you decided to choose 22 for the next turn, only a single instance of 22will be deleted (and added to the score, if necessary).

The player A starts the game and the game stops when both lists are empty. Find the difference between A's score and B's score at the end of the game, if both of the players are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves. In this problem, it means that each player, each time makes a move, which maximizes the final difference between his score and his opponent's score, knowing that the opponent is doing the same.

Input

The first line of input contains an integer nn (1≤n≤1000001≤n≤100000) — the sizes of the list.

The second line contains nn integers aiai (1≤ai≤1061≤ai≤106), describing the list of the player A, who starts the game.

The third line contains nn integers bibi (1≤bi≤1061≤bi≤106), describing the list of the player B.

Output

Output the difference between A's score and B's score (A−BA−B) if both of them are playing optimally.

Examples

Input

2
1 4
5 1

Output

0

Input

3
100 100 100
100 100 100

Output

0

Input

2
2 1
5 6

Output

-3

Note

In the first example, the game could have gone as follows:

  • A removes 55 from B's list.
  • B removes 44 from A's list.
  • A takes his 11.
  • B takes his 11.

Hence, A's score is 11, B's score is 11 and difference is 00.

There is also another optimal way of playing:

  • A removes 55 from B's list.
  • B removes 44 from A's list.
  • A removes 11 from B's list.
  • B removes 11 from A's list.

The difference in the scores is still 00.

In the second example, irrespective of the moves the players make, they will end up with the same number of numbers added to their score, so the difference will be 00.

题目大意：

有A,B两个竞赛者各自拥有一个序列，他们可以在每一个回合中可以任意进行两种操作的其中一种，第一种操作是在对方的序列中删除一个元素，第二种操作是把自己序列中的一个元素加入自己的得分中，A,B都想要自己的得分较高，输出A-B的值。

解题报告：

    这题贪心，用优先队列模拟一下，也可以直接数组模拟一下，不难做，有一个类似的题目需要用dp去求解【UVA - 10891 Game of Sum 】dp，博弈

    对于这题注意一下a为空或者b为空的情况就可以了。

   另外。代码格式方面，建议while(1)然后if（..）break;elseif();elseif();else这样的格式，这样层次分明，并且不会拉下a为空或者b为空的情况，一开始写代码的时候就落下了这两种情况。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll tmp,suma,sumb;
priority_queue<ll> a,b;
int main()
{
	int n;
	bool flag = 1;//1代表先手a，2代表后手b 
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%lld",&tmp),a.push(tmp);
	for(int i = 1; i<=n; i++) scanf("%lld",&tmp),b.push(tmp);
	while(a.size() || b.size()) {
		if(a.empty()) {
			if(!flag) sumb += b.top();
			b.pop();
			flag = !flag;
			continue;
		}
		if(b.empty()) {
			if(flag) suma += a.top();
			a.pop();
			flag = !flag;
			continue; 
		}
		if(flag) {
			if(a.top() >= b.top()) {
				suma += a.top();
				a.pop();
			} 
			else {
				b.pop();
			}
		}
		else {
			if(b.top() >= a.top()) {
				sumb += b.top();
				b.pop();
			}
			else {
				a.pop();
			}
		}
		flag = !flag;
	} 
	printf("%lld\n",suma - sumb);
	return 0 ;
}

//18:04 - 18:17