Palembang Bridges

The Musi River runs through the city of Palembang and splits it into two districts. Call them district A and district B.

Each district has exactly 1,000,000,001 buildings along the bank, numbered 0 to 1,000,000,000 in order. Two neighbouring buildings are 1 unit apart, and the river is 1 unit wide. Building $i$ of district A sits directly across the river from building $i$ of district B.

$N$ citizens live and work in the city. Citizen $i$ lives in building $S_i$ of district $P_i$ and works in building $T_i$ of district $Q_i$. A citizen whose home and office are in different districts has had to cross the river by boat. Boats are inconvenient, so the city wants to build at most $K$ bridges so that every citizen can commute by car alone. A bridge must be perpendicular to the river, so it joins two buildings with the same number, and two different bridges use different numbers.

After the bridges are built, let $D_i$ be the shortest distance citizen $i$ can drive from home to the office. Place the bridges so that $D_1 + D_2 + \cdots + D_N$ is as small as possible, and report that minimum.

The first line contains $K$ and $N$. Each of the next $N$ lines contains $P_i$, $S_i$, $Q_i$, $T_i$, separated by spaces.

• $P_i$ and $Q_i$ are the single character 'A' or 'B'.
• $0 \le S_i, T_i \le 10^9$
• $1 \le K \le 2$
• $1 \le N \le 100\,000$
• Two different citizens may have their homes or offices in the same building, and one citizen's home may be the same building as another citizen's office.

Print the minimum total commuting distance on one line.

This picture shows both example inputs.

One optimal placement for the first example. The pink part is the bridge.

One optimal placement for the second example.