Person in charge

• 035966_L3

Attention

This problem requires file I/O (pairs.in / pairs.out).

Problem Background

Sleeping Allegator is the manager of a sleeper train car. The car has several beds, each with an upper and lower berth (each bed can accommodate $2$ people). One day, while the car was fully occupied, the power suddenly went out!

This immediately angered the passengers. They demanded that Sleeping Allegator resolve the issue by relocating them to another car. At the same time, some passengers complained that their upper (or lower) berth neighbors snored, making it impossible for them to sleep.

Problem Description

Sleeping Allegator summarizes the problem it needs to solve:

• The car has $n$ beds, each with an upper and lower berth.
• Each berth is occupied by a passenger. Some passengers snore (denoted by Z), while others do not (denoted by X).
• Passengers want the upper and lower berths of the same bed to have the same attribute (whether they snore or not).
• Sleeping Allegator can perform the following operations, each costing $\bm 1$ unit of energy per operation (only one operation can be chosen at a time):
  • Swap two adjacent passengers (upper berths of adjacent beds, lower berths of adjacent beds, or upper and lower berths of the same bed).
  • Remove a bed whose berths already meet the passengers' expectations.
• The goal is to remove all beds (guaranteed to be possible). What is the minimum energy required?

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain $2$ characters, indicating of information about the persons on the upper and lower berths in each bed.

Output Format

A single positive integer representing the answer.

Samples

3
XZ
ZZ
ZX

4

18
XX
XX
XX
XX
XZ
ZX
XZ
ZZ
XZ
XZ
ZZ
XZ
ZX
XZ
XX
XX
XX
XX

24

Explanation for Sample 1

One optimal solution is:

• Remove the second bed.
• Swap the the persons on the remaining two upper (otr lower) berths.
• Remove the remaining two beds.
• Total energy cost: $4$.

Data Range

For $100\%$ of the data: $1 \le n \le 10^5$.

The counts of X and Z are both even (ensuring the goal is achievable).

Official Solution

link