Kết nối điểm

Trên trục số, Roy và Biv có một tập hợp gồm \(n\) điểm, mỗi điểm có vị trí và màu sắc. Mỗi điểm là một trong ba màu: đỏ (R), xanh lá (G) hoặc xanh dương (B).

Họ muốn nối các điểm lại bằng những đoạn thẳng (cạnh). Mỗi cạnh có thể nối hai điểm bất kỳ, và chi phí của cạnh chính là khoảng cách giữa hai điểm được nối.

Mục tiêu là chọn một số cạnh sao cho toàn bộ \(n\) điểm được kết nối (trực tiếp hoặc gián tiếp). Tuy nhiên, có một điều đặc biệt:

• Roy không nhìn thấy màu đỏ.
• Biv không nhìn thấy màu xanh dương.

Do đó, họ muốn chọn các cạnh sao cho:

• Nếu bỏ toàn bộ điểm màu đỏ, thì các điểm còn lại (xanh lá và xanh dương) vẫn phải kết nối được với nhau.
• Nếu bỏ toàn bộ điểm màu xanh dương, thì các điểm còn lại (xanh lá và đỏ) cũng phải kết nối được với nhau.

Hãy giúp họ tìm cách kết nối các điểm với tổng chi phí nhỏ nhất, thoả mãn hai điều kiện trên.

Chú ý: Tọa độ các điểm là phân biệt và tăng dần.

Hai điểm được xem là "kết nối với nhau" nếu tồn tại chuỗi các cạnh nối giữa chúng.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 300\,000\)) --- số lượng điểm.
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(p_i\) (\(1 \le p_i \le 10^9\)) và một ký tự \(c_i\) (\(c_i \in \{R, G, B\}\)) --- tọa độ và màu sắc của điểm thứ \(i\).
• Các tọa độ \(p_i\) là phân biệt và tăng dần.

\OutputFile

In ra chi phí nhỏ nhất cần thiết để kết nối các điểm, thỏa mãn điều kiện của Roy và Biv.

\Scoring

• Subtask 1 (10 điểm): tất cả các điểm chỉ có màu G.
• Subtask 2 (11 điểm): không có điểm nào có màu G.
• Subtask 3 (15 điểm): tất cả các điểm có màu R hoặc màu G.
• Subtask 4 (17 điểm): \(n \le 10\).
• Subtask 5 (47 điểm): không có ràng buộc gì thêm.

Example

4
1 G
4 R
8 B
15 G

24