RGB Matching

AtCoder

IDarc121_b

Time2000ms

Memory256MB

Difficulty—

Snuke has $2N$ dogs, numbered $1$ through $2N$. The cuteness of Dog $i$ is $a_i$. The color of Dog $i$ is $c_i$, which is `R`, `G`, or `B`; `R` stands for red, `G` stands for green, and `B` stands for blue. Snuke has $N$ kennels, and wants to put two dogs in each kennel. Note that this means each dog will be in exactly one kennel. When he puts two dogs in the same kennel, it will cause some _dissatisfaction_ in that kennel. The level of dissatisfaction is represented as an integer. When Dogs $i$ and $j$ are in the same kennel, the dissatisfaction will be $0$ if $c_i = c_j$ and $|a_i - a_j|$ otherwise. Find the minimum possible total dissatisfaction when putting two dogs in each of the $N$ kennels. ## Constraints * $1 \leq N \leq 10^{5}$ * $1 \leq a_i \leq 10^{15}$ * $a_i$ is an integer. * $c_i$ is `R`, `G`, or `B`. ## Input Input is given from Standard Input in the following format: $N$ $a_{1}$ $c_{1}$ $\vdots$ $a_{2N}$ $c_{2N}$ [samples]

Samples

Input #1

1
1 R
2 G

Output #1

1

*   Dog $1$ has the cuteness of $1$, and Dog $2$ has the cuteness of $2$.
*   Since $c_1 \neq c_2$, the dissatisfaction will be $1$.

Input #2

1
1 B
2 B

Output #2

0

*   Dog $1$ has the cuteness of $1$, and Dog $2$ has the cuteness of $2$.
*   Since $c_1 = c_2$, the dissatisfaction will be $0$.

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "RGB Matching",
    "description": {
      "content": "Snuke has $2N$ dogs, numbered $1$ through $2N$. The cuteness of Dog $i$ is $a_i$. The color of Dog $i$ is $c_i$, which is `R`, `G`, or `B`; `R` stands for red, `G` stands for green, and `B` stands for",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc121_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke has $2N$ dogs, numbered $1$ through $2N$.\nThe cuteness of Dog $i$ is $a_i$. The color of Dog $i$ is $c_i$, which is `R`, `G`, or `B`; `R` stands for red, `G` stands for green, and `B` stands for...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments