题目描述

すぬけ君养了 $2N$ 只编号为 $1$ 到 $2N$ 的狗。

第 $i$ 只狗的可爱度为 $a_i$。每只狗的体色为红、绿或蓝中的一种，第 $i$ 只狗的体色为 $c_i$。$c_i$ 是 R、G、B 之一，R 表示红色，G 表示绿色，B 表示蓝色。

すぬけ君有 $N$ 间狗舍，他打算每间狗舍住进 $2$ 只狗。需要保证每只狗恰好住进一间狗舍。

当两只狗住进同一间狗舍时，这间狗舍会产生“不满”。不满程度用整数表示，若第 $i$ 只狗和第 $j$ 只狗住在同一间狗舍，若 $c_i = c_j$，则不满为 $0$，否则为 $|a_i - a_j|$。

请你求出将 $2N$ 只狗分配到 $N$ 间狗舍，每间狗舍住 $2$ 只狗后，可能产生的不满总和的最小值。

输入格式

输入按以下格式从标准输入读入。

$N$
$a_1$ $c_1$
$a_2$ $c_2$
$\vdots$
$a_{2N}$ $c_{2N}$

输出格式

请输出将 $2N$ 只狗分配到 $N$ 间狗舍，每间狗舍住 $2$ 只狗后，可能产生的不满总和的最小值。

样例 1

输入

1
1 R
2 G

输出

1

样例 2

输入

1
1 B
2 B

输出

0

样例 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

输出

0

说明/提示

限制条件

• $1 \leq N \leq 10^{5}$
• $1 \leq a_i \leq 10^{15}$
• $a_i$ 是整数
• $c_i$ 是 R、G、B 之一

样例解释 1

• 第 $1$ 只狗的可爱度为 $1$，第 $2$ 只狗的可爱度为 $2$。
• 因为 $c_1 \neq c_2$，所以不满为 $1$。

样例解释 2

• 第 $1$ 只狗的可爱度为 $1$，第 $2$ 只狗的可爱度为 $2$。
• 因为 $c_1 = c_2$，所以不满为 $0$。

由 ChatGPT 4.1 翻译