Thành phố Palembang bị sông Musi chia thành hai vùng \(A\) và \(B\). Mỗi vùng có đúng \(1\,000\,000\,001\) tòa nhà dọc bờ sông, đánh số từ \(0\) đến \(1\,000\,000\,000\). Hai tòa nhà liền kề cách nhau một đơn vị; bề rộng sông cũng là một đơn vị. Tòa nhà \(i\) ở vùng \(A\) đối diện tòa nhà \(i\) ở vùng \(B\).

Có \(N\) công dân. Nhà của người \(i\) ở tòa nhà \(S_i\) thuộc vùng \(P_i\), còn nơi làm việc ở tòa nhà \(T_i\) thuộc vùng \(Q_i\). Chính phủ sẽ xây tối đa \(K\) cây cầu. Mỗi cầu nối hai tòa nhà đối diện ở hai vùng, vuông góc với sông, và các cầu không chồng lên nhau.

Sau khi xây cầu, gọi \(D_i\) là khoảng cách lái xe ngắn nhất từ nhà đến nơi làm việc của công dân \(i\). Hãy chọn vị trí cầu để tối thiểu hóa:

Dữ liệu vào

• Dòng đầu chứa \(K,N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(P_i,S_i,Q_i,T_i\). Hai giá trị \(P_i,Q_i\) là ký tự A hoặc B; các trường còn lại là số nguyên.

Dữ liệu ra

In tổng khoảng cách nhỏ nhất.

Ràng buộc chung

• \(P_i,Q_i\in\{\texttt{A},\texttt{B}\}\).
• \(0\le S_i,T_i\le1\,000\,000\,000\).
• Nhiều nhà hoặc nơi làm việc có thể nằm trong cùng một tòa nhà.

Ví dụ

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

24

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

22

Giải thích

Cấu hình thành phố trong cả hai ví dụ:

{{asset:apio15-bridge-initial}}

Ở ví dụ thứ nhất chỉ có một cách đặt cầu tối ưu:

{{asset:apio15-bridge-sample1}}

Một cách đặt hai cầu tối ưu cho ví dụ thứ hai:

{{asset:apio15-bridge-sample2}}

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2015, bài Palembang Bridges.