#S4. [ARC121B] RGB Matching

[ARC121B] RGB Matching

[ARC121B] RGB Matching

题面翻译

Pretharp 有 2N2N 块巧克力,第 ii 块巧克力有一个美味程度 aia_i 和一个颜色 ci={A,B,C}c_i=\{\texttt{A},\texttt B,\texttt C\}。现在 Pretharp 要把这 2N2N 块巧克力放入 NN 个盒子,每个盒子恰好放 22 块巧克力且每块巧克力必须在一个盒子当中,接下来:

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

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

题目描述

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

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

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

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

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

输入格式

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

N N a1 a_{1} c1 c_{1} \vdots a2N a_{2N} c2N c_{2N}

输出格式

N N 棟の犬小屋に犬を 2 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  N  105 1\ \leq\ N\ \leq\ 10^{5}
  • 1  ai  1015 1\ \leq\ a_i\ \leq\ 10^{15}
  • ai a_i は整数
  • ci c_i R, G, B のいずれか

Sample Explanation 1

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

Sample Explanation 2

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

Statistics

Related

In following homework:

S组训练计划