Problem Description

A river, running east to west, divides the city of Palembang into two regions, $A$ and $B$.

Each region has exactly $1000000001$ buildings along the riverbank, numbered from $0$ to $1000000000$. Adjacent buildings are $1$ unit apart, and the width of the river is also $1$ unit. The $i$-th building in region $A$ is directly opposite the $i$-th building in region $B$.

The city has $N$ residents. The $i$-th resident's home is located at building $S_i$ in region $P_i$, and their office is at building $T_i$ in region $Q_i$. A resident's home and office may be on opposite sides of the river, requiring them to take a boat to commute, which is inconvenient for many. To allow residents to drive to work, the government plans to build no more than $K$ bridges across the river.

Due to technical reasons, each bridge must connect both riverbanks directly, be perpendicular to the river, and not intersect with other bridges.

After the government builds up to $K$ bridges, let $D_i$ represent the shortest driving distance for the $i$-th resident to commute from home to office. Help the government build the bridges to minimize $D_1 + D_2 + \cdots + D_N$.

Input Format

The first line of input contains two positive integers $K$ and $N$, representing the maximum number of bridges and the number of residents, respectively.

The next $N$ lines each contain four parameters: $P_i, S_i, Q_i,$ and $T_i$, indicating that the $i$-th resident's home is at building $S_i$ in region $P_i$, and their office is at building $T_i$ in region $Q_i$.

Output Format

Output a single line containing an integer, which is the minimum value of $D_1 + D_2 + \cdots + D_N$.

Sample Input and Output

Input Sample #1

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Output Sample #1

24

Input Sample #2

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Output Sample #2

22

Notes

Data Range:

All data guarantees: $P_i$ and $Q_i$ are either 'A' or 'B', $0 \leq S_i, T_i \leq 1000000000$. There may be more than one home or office in the same building.

• Subtask 1 (8 points): $K = 1$, $1 \leq N \leq 1000$
• Subtask 2 (14 points): $K = 1$, $1 \leq N \leq 100000$
• Subtask 3 (9 points): $K = 2$, $1 \leq N \leq 100$
• Subtask 4 (32 points): $K = 2$, $1 \leq N \leq 1000$
• Subtask 5 (37 points): $K = 2$, $1 \leq N \leq 100000$

见题面 Input 部分

见题面 Output 部分