Bridge Construction Optimization

A river called Musi flows east–west and divides the city into two regions, (A) and (B). Each region has exactly (10^9+1) buildings built along the river bank, numbered from (0) to (10^9). Adjacent buildings are separated by a distance of (1), and the river’s width is also (1). In region (A), the building with index (i) is directly opposite the building with index (i) in region (B).

There are (N) residents in the city. The (i)th resident lives in building (S_i) in region (P_i) and works in building (T_i) in region (Q_i). Note that a resident’s home and office may be on different sides of the river. In that case the resident must normally take a boat, which many find inconvenient. In order to let all residents drive to work, the government has decided to build no more than (K) bridges across the river.

Because of technical constraints, each bridge must:

• Connect a building in region \(A\) with the building directly opposite it in region \(B\) (i.e. at the same building index);
• Be built strictly perpendicular to the river; and
• Not intersect any other bridge.

After constructing at most (K) bridges, let (D_i) be the minimum driving distance for the (i)th resident from home to the office. For a resident whose home and office are on the same side, (D_i=|S_i-T_i|). For a resident whose home and office are on different sides, if a bridge is built at some position (x) ((0\le x\le10^9)), the driving distance is (|S_i-x|+1+|T_i-x|) (the extra (1) unit is the width of the river). Since a resident can choose any of the built bridges, his driving distance is the minimum value over all built bridges.

In other words, if we define (A_i=\min(S_i,T_i)) and (B_i=\max(S_i,T_i)) for residents with (P_i\ne Q_i), then when using a bridge built at (x), the distance is (|S_i-T_i|+1+) extra penalty, where for each such resident the extra penalty is (0) if (x\in [A_i, B_i]) and otherwise (2,\min(|x-A_i|,|x-B_i|)).

The government wants to choose the positions of at most (K) bridges to minimize (D_1+D_2+\cdots+D_N).

Your task is to compute this minimum total driving distance.

Input Format: The input starts with two integers (N) and (K). Then (N) lines follow. The (i)th line contains a character (P_i) (either 'A' or 'B'), an integer (S_i), a character (Q_i) (either 'A' or 'B'), and an integer (T_i).

Output Format: Output a single integer which is the minimum possible (D_1+D_2+\cdots+D_N) after building at most (K) bridges.

Note: For residents with (P_i=Q_i), no bridge is needed and (D_i=|S_i-T_i|). For residents with (P_i\ne Q_i), if a bridge is built in an optimal position, the driving distance becomes (|S_i-T_i|+1) when the built bridge lies in the interval ([A_i, B_i]); if not, an extra penalty is added. The additional cost for a group of cross‐river trips served by a single bridge can be computed as: [ \text{GroupCost} = \sum_{i}(B_i-A_i+1) + \max\Big(0, 2\Big(\max_{i}A_i - \min_{i}B_i\Big)\Big). ]

It is optimal to partition the cross‐river trips (where (P_i\ne Q_i)) into several groups (each served by one bridge) so that the overall total cost is minimized.

Constraints: You may assume that the number of cross‐river trips is small enough for an (O(N^2K)) solution to pass.

inputFormat

The first line contains two integers \(N\) and \(K\), where \(1 \le N \le \text{(small)}\). Each of the next \(N\) lines contains a character \(P_i\) (either 'A' or 'B'), an integer \(S_i\), a character \(Q_i\) (either 'A' or 'B'), and an integer \(T_i\), separated by spaces.

It is guaranteed that when \(P_i = Q_i\) the driving distance is simply \(|S_i-T_i|\), and when \(P_i \ne Q_i\) the driving distance (if a suitable bridge is used) is \(|S_i-T_i|+1\) plus a possible additional penalty.

outputFormat

Output one integer: the minimum total driving distance \(D_1+D_2+\cdots+D_N\) after building at most \(K\) bridges.

sample

3 1
A 0 B 10
A 5 A 8
B 2 A 4

17