Chỉ còn vài ngày nữa thôi là chúng ta sẽ đón Tết Nguyên Đán, gia đình của TINEZ đang tất bật chuẩn bị quần áo mới và lên kế hoạch đi du xuân đầu năm. Có ~N~ (~1~ ~\leq~ ~N~ ~\leq~ ~16~) địa điểm mà gia đình của TINEZ muốn đi thăm vào những ngày đầu năm mới này. Mỗi địa điểm chỉ được thăm đúng 1 lần và sau khi thăm hết N địa điểm đó thì cả nhà sẽ quay trở về địa điểm bắt đầu. Giữa 2 vị trí ~u~ và ~v~ (~1~ ~\leq~ ~u~, ~v~ ~\leq~ ~N~) có 1 con đường 2 chiều giữa 2 vị trí đó. Thế nhưng, việc di chuyển giữa 2 địa điểm ~u~ và ~v~ sẽ khiến gia đình của TINEZ tốn ~c_{u,v} = c_{v,u}~ (đồng) (~0~ ~\leq~ ~c_{u,v} = c_{v,u}~ ~\leq~ ~10^6~) tiền đổ xăng để di chuyển qua tuyến đường này. Gia đình của TINEZ đang không biết liệu rằng lượng tiền đổ xăng ít nhất cần phải chi để đi qua tất cả các địa điểm này. TINEZ hiện tại đang bận chơi Tết nên quên hết cách code để tìm ra phương án cho bài toán “hóc búa” này nên anh ấy muốn nhờ bạn giải quyết bài toán này.

Input

• Dòng đầu chứa số nguyên ~N~ là số địa điểm
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số ~c_{u,v}~ là chi phí để di chuyển giữa 2 vị trí ~u~ và ~v~

Output

• Đưa ra 1 số duy nhất chính là chi phí nhỏ nhất để thăm tất cả ~N~ địa điểm sau đó quay về địa điểm bắt đầu

Constraint

• ~1~ ~\leq~ ~N~ ~\leq~ ~16~
• ~1~ ~\leq~ ~u,v~ ~\leq~ ~N~
• ~0~ ~\leq~ ~c_{u,v}~ ~\leq~ ~10^6~

Subtasks

• Subtask 1 (80%): ~N~ ~\leq~ ~10~
• Subtask 2 (20%): ~10~ ~<~ ~N~ ~\leq~ ~16~

Sample Input

4
0 10 15 20
10 0 25 25
15 25 0 30
20 25 30 0

Sample Output

80

Notes

Một phương án đi hết tất cả các địa điểm là: ~1 \to 2 \to 4 \to 3 \to 1~. Và đây cũng là phương án có chi phí nhỏ nhất: ~10 + 25 + 30 + 15 = 80~.