Thành phố Palembang bị dòng sông Musi chia cắt thành hai phần. Ta sẽ gọi chúng là vùng \(A\) và vùng \(B\). Mỗi vùng bao gồm đúng \(1,000,000,001\) toà nhà chạy dọc theo bờ sông được đánh số từ 0 đến \(10^9\). Khoảng cách giữa mỗi cặp toà nhà liền kề là 1 đơn vị khoảng cách. Bề rộng của dòng sông cũng là 1 đơn vị khoảng cách. Toà nhà \(i\) ở vùng \(A\) là đối diện với toà nhà \(i\) ở vùng \(B\).

Có \(N\) công dân sống và làm việc trong thành phố. Nhà của công dân \(i\) trong vùng \(P_i\) ở toà nhà \(S_i\), trong khi đó trụ sở cơ quan làm việc của công dân này lại ở vùng \(Q_i\) toà nhà \(T_i\). Khi đi từ nhà đến trụ sở làm việc (khác vùng với nhà) thì công dân phải vượt qua sông bằng thuyền. Điều đó là hết sức bất tiện cho người dân, vì thế chính phủ quyết định xây dựng 1 cây cầu qua sông để các công dân có thể lái xe đi làm. Cây cầu phải được xây dựng giữa đúng hai toà nhà đối diện ở hai vùng. Cây cầu phải vuông góc với dòng sông.

Ký hiệu \(D_i\) là khoảng cách nhỏ nhất mà công dân \(i\) phải lái xe từ nhà của mình đến trụ sở làm việc sau khi chính phủ xây dựng xong 1 cây cầu. Hãy giúp chính phủ tìm phương án xây dựng 1 cây cầu sao cho tổng \(D_1 + D_2 + ... + D_N\) là nhỏ nhất.

Input:

• Dòng đầu tiên chứa số nguyên \(N\).

• Mỗi dòng trong \(N\) dòng tiếp theo chứa 4 thông số \(P_i, S_i, Q_i và T_i\).

Output :

• Một dòng duy nhất chứa tổng khoảng cách nhỏ nhất

Sample input:

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

Sample output:

24

Giới hạn:

0 ≤ \(S_i, T_i\) ≤ \(10^9\). Có thể có nhiều hơn 1 căn hộ hoặc trụ sở cơ quan (hoặc tổ hợp cả hai) thuộc cùng một toà nhà.

Subtask 1 :\(1 ≤ N ≤ 1000\);

Subtask 2 : \(1 ≤ N ≤ 100000\);