Pha thuốc 5

Reimu có \(n \times 2\) cây nấm và cô ấy muốn pha \(n\) chai thuốc, mỗi chai sử dụng chính xác \(2\) cây nấm. Nếu cây nấm thứ \(i\) được kết hợp với cây nấm thứ \(j\), thì thuốc có sức mạnh là \(A_{i,j}\). Reimu muốn tìm cách tối đa hóa tổng sức mạnh của \(n\) chai thuốc.

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 10\)).

• \(n \times 2\) dòng tiếp theo, dòng \(i\) gồm \(n \times 2\) số nguyên \(A_{i,j}\) (\(0 \le |A_{i,j}| \le 10^6\)). Đảm bảo \(A_{i,j} = A_{j,i}\).

Output

In ra tổng sức mạnh lớn nhất của \(n\) chai thuốc.

Example

Input:

1
0 -2
-2 0

Output:

-2

Note

Với \(n = 1\), chỉ có \(2\) cây nấm (chỉ số \(0\) và \(1\)), bắt buộc phải pha chung thành \(1\) chai thuốc với sức mạnh \(A_{0,1} = -2\), nên tổng sức mạnh lớn nhất là \(-2\).