問題一覧 > 通常問題

No.2856 Junk Market Game

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 74
作問者 : dyktr_06 / テスター : ryota2357 square1001 sepa38
お気に入りにしたユーザー ProblemId : 10857 / 自分の提出
問題文最終更新日: 2024-08-20 19:22:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 442 MMA Contest 019 (順位表) の他の問題:

Problem Statement

At MMA's junk market, $2N$ items are on sale, $1$ of each.

The $i$-th item can be purchased by a general customer for $A_i$ yen, and by an MMA member for $B_i$ yen.

A general customer and an MMA member play a game. With the general customer going first and the MMA member going second, they alternately repeat the following operation.

  • Choose $1$ item of the junk market that has not been purchased yet, and purchase it.

The game ends when all items of the junk market have been purchased.

Let $X$ be the amount paid by the general customer and $Y$ be the amount paid by the MMA member. The general customer tries to minimize $X - Y$, and the MMA member tries to maximize $X - Y$.

Find the value of $X - Y$ when both act optimally.


Constraints

  • $1 \leq N \leq 1000$
  • $1 \leq A_i, B_i \leq 10^{9}$
  • All inputs are integers.

Input

The input is given from standard input in the following format.

$N$
$A_1$ $A_2$ ... $A_{2N}$ 
$B_1$ $B_2$ ... $B_{2N}$  

Output

Output the answer to the problem on one line.

Sample

Sample 1
Input
1
100 200
150 300
Output
-200

If the general customer purchases the $1$st item, the MMA member has no choice but to purchase the $2$nd item, so $X - Y = 100 - 300 = -200$.

Sample 2
Input
3
100 200 350 400 550 600
400 200 300 100 150 500
Output
-50

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。