Cho một đa đồ thị vô hướng gồm ~n~ đỉnh và ~2n~ cạnh. Các đỉnh được đánh số từ ~1~ đến ~n~, các cạnh được đánh số từ ~1~ đến ~2n~.

Mỗi cạnh nối hai đỉnh phân biệt; có thể có nhiều cạnh cùng nối một cặp đỉnh. Mỗi đỉnh của đồ thị liên thuộc với đúng bốn cạnh. Danh sách các cạnh liên thuộc với đỉnh ~u~ theo thứ tự là:

~e_{(u,1)},e_{(u,2)},e_{(u,3)},e_{(u,4)}~.

Một vị trí trong đồ thị là một cặp ~(u,id)~, thể hiện bạn đang ở đỉnh ~u~ và liên kết với cạnh ~e_{(u,id)}~. Có hai loại di chuyển:

• Thay đổi đỉnh: Nếu ~e_{(u,id)}=(u,v)~ thì đi từ đỉnh ~u~ đến đỉnh ~v~ và vẫn liên kết với cạnh vừa đi qua;

• Thay đổi hướng: Nếu đang liên kết với ~e_{(u,1)}~ thì chuyển sang ~e_{(u,2)}~ và ngược lại; nếu đang liên kết với ~e_{(u,3)}~ thì chuyển sang ~e_{(u,4)}~ và ngược lại.

Có tất cả ~4n~ vị trí trong đồ thị. Để làm cho tất cả các vị trí này có thể đi đến nhau, có thể sửa danh sách cạnh liên thuộc của một số đỉnh bằng cách thay đổi thứ tự của danh sách theo một hoán vị bất kỳ. Chi phí sửa danh sách của đỉnh ~u~ là ~c_u~.

Yêu cầu: Hãy xác định tổng chi phí nhỏ nhất để làm cho tất cả ~4n~ vị trí trở nên liên thông.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 10^5)~;

• Dòng thứ ~i+1~ với ~1 \le i \le n~ chứa năm số nguyên ~c_i,e_{(i,1)},e_{(i,2)},e_{(i,3)},e_{(i,4)}~ ~(1 \le c_i \le 1000)~;

• Dữ liệu bảo đảm ~e_{(i,j)}\ne e_{(i,t)}~ với mọi ~j\ne t~. Mỗi cạnh nối hai đỉnh ~u,v~ luôn xuất hiện trong danh sách cạnh liên thuộc của cả ~u~ và ~v~.

Output

Một số nguyên duy nhất là tổng chi phí nhỏ nhất cần thực hiện.

Scoring

Sample Input 1

5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5

Sample Output 1

13

Notes

Có thể sửa danh sách cạnh liên thuộc của đỉnh ~1~ và đỉnh ~4~ thành:

• ~e(1)\leftarrow(1,9,4,8)~;

• ~e(4)\leftarrow(7,4,6,3)~.

Tổng chi phí là ~c_1+c_4=10+3=13~.