題干：

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的值。

解題報告：

? ? 這題貪心，用優(yōu)先隊列模擬一下，也可以直接數(shù)組模擬一下，不難做，有一個類似的題目需要用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

?

總結

以上是生活随笔為你收集整理的【CodeForces - 1038C】Gambling （博弈问题，优先队列模拟，贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。