You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC121B] RGB Matching

题面翻译

Pretharp 有 $2N$ 块巧克力，第 $i$ 块巧克力有一个美味程度 $a_i$ 和一个颜色 $c_i=\{\texttt{A},\texttt B,\texttt C\}$。现在 Pretharp 要把这 $2N$ 块巧克力放入 $N$ 个盒子，每个盒子恰好放 $2$ 块巧克力且每块巧克力必须在一个盒子当中，接下来：

• 如果一个盒子的两个巧克力颜色一样，Pretharp 会把它们吃掉。
• 如果一个盒子的两个巧克力颜色不一样，Pretharp 会产生两个巧克力美味程度之差的绝对值（即 $|a_i-a_j|$）的不满意值。

现在求怎样放置巧克力让挑剔的 Pretharp 不满意程度最小，输出最小值。

题目描述

すぬけ君は $1$ から $2N$ の番号がついた $2N$ 匹の犬を飼っています。

犬 $i$ のかわいさは $a_i$ です。 それぞれの犬の体色は赤、緑、青のいずれかで、犬 $i$ の体色は $c_i$ です。 $c_i$ は R, G, B のいずれかであり、R ならばその犬の体色が赤であることを、G ならば緑であることを、B ならば青であることを表します。

すぬけ君は $N$ 棟の犬小屋を持っており、それぞれの犬小屋に $2$ 匹の犬を住まわせようとしています。 どの犬もちょうど一つの犬小屋に住んでいるように住まわせる必要があることに注意してください。

$2$ 匹の犬を同じ犬小屋に住まわせるとその小屋には 不満 が生じます。 不満の度合いは整数で表され、犬 $i,j$ が同じ小屋にいるとき生じる不満は $c_i\ =\ c_j$ ならば $0$、そうでなければ $|a_i\ -\ a_j|$ です。

$N$ 棟の犬小屋に犬を $2$ 匹ずつ住まわせた結果生じる不満の総和としてありうる値の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_{1}$ $c_{1}$ $\vdots$ $a_{2N}$ $c_{2N}$

输出格式

$N$ 棟の犬小屋に犬を $2$ 匹ずつ住まわせた結果生じる不満の総和としてありうる値の最小値を出力せよ。

样例 #1

样例输入 #1

1
1 R
2 G

样例输出 #1

1

样例 #2

样例输入 #2

1
1 B
2 B

样例输出 #2

0

样例 #3

样例输入 #3

10
585 B
293 B
788 B
222 B
772 G
841 B
115 R
603 G
450 B
325 R
851 B
205 G
134 G
651 R
565 R
548 B
391 G
19 G
808 B
475 B

样例输出 #3

0

提示

制約

• $1\ \leq\ N\ \leq\ 10^{5}$
• $1\ \leq\ a_i\ \leq\ 10^{15}$
• $a_i$ は整数
• $c_i$ は R, G, B のいずれか

Sample Explanation 1

- 犬 $1$ のかわいさは $1$、犬 $2$ のかわいさは $2$ です。 - $c_1\ \neq\ c_2$ より、不満は $1$ となります。

Sample Explanation 2

- 犬 $1$ のかわいさは $1$、犬 $2$ のかわいさは $2$ です。 - $c_1\ =\ c_2$ より、不満は $0$ となります。