팔렘방의 다리

팔렘방 시에는 무시강이 흘러 도시가 두 구역으로 나뉜다. 두 구역을 구역 A와 구역 B라고 하자.

각 구역에는 강변을 따라 빌딩이 정확히 1,000,000,001개 있고, 0번부터 1,000,000,000번까지 번호가 붙어 있다. 이웃한 두 빌딩 사이의 거리는 1이고 강의 폭도 1이다. 구역 A의 빌딩 $i$는 구역 B의 빌딩 $i$와 강을 사이에 두고 정확히 마주 본다.

시민 $N$명이 이 도시에서 살면서 일한다. 시민 $i$는 구역 $P_i$의 빌딩 $S_i$에 살고, 사무실은 구역 $Q_i$의 빌딩 $T_i$에 있다. 사는 곳과 사무실이 서로 다른 구역에 있으면 지금까지는 배로 강을 건너야 했다. 배를 타는 일이 번거롭기 때문에 시는 다리를 최대 $K$개 놓아서 모든 시민이 자동차로만 출근하게 만들려고 한다. 다리는 강과 수직이어야 하므로 같은 번호의 두 빌딩을 잇고, 서로 다른 다리는 서로 다른 번호에 놓인다.

다리를 다 놓은 뒤 시민 $i$가 집에서 사무실까지 자동차로 이동하는 최소 거리를 $D_i$라고 하자. $D_1 + D_2 + \cdots + D_N$이 최소가 되도록 다리를 놓았을 때 그 최솟값을 구하라.

첫 줄에 $K$와 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 $P_i$, $S_i$, $Q_i$, $T_i$가 공백으로 구분되어 주어진다.

• $P_i$와 $Q_i$는 한 글자 'A' 또는 'B'이다.
• $0 \le S_i, T_i \le 10^9$
• $1 \le K \le 2$
• $1 \le N \le 100\,000$
• 서로 다른 시민의 집이나 사무실이 같은 빌딩에 있을 수 있고, 한 시민의 집이 다른 시민의 사무실과 같은 빌딩일 수도 있다.

출근 거리 합의 최솟값을 한 줄에 출력한다.

두 예제 입력을 함께 나타낸 그림이다.

첫 번째 예제의 답이 되는 배치 하나이다. 분홍색 부분이 다리이다.

두 번째 예제의 답이 되는 배치 하나이다.