Ban quản lý thành phố X quyết định phạt tiền bạn vì đỗ xe trái phép. Tuy nhiên vì ban quản lý đều rất tốt bụng, họ quyết định cho bạn chọn tiền phạt của chính mình. Thậm chí nếu tiền phạt là số âm, bạn sẽ được thưởng thêm tiền!

Bạn được cho số nguyên dương ~N~ và ~N~ số nguyên ~s_1, s_2, …, s_N~. Ban đầu các số ~s_i~ đều có giá trị là 1.

Mỗi lượt bạn được phép chọn một số ~s_i~ bất kỳ và đổi dấu số đó (1 thành -1, -1 thành 1).

Với mỗi số ~s_i~ ~(1 \leq i \leq N)~, bạn bị phạt lượng tiền là ~h_i*s_i~. Ngoài ra với mỗi cặp số ~s_i, s_j~ ~(1 \leq i < j \leq N)~, bạn bị phạt lượng tiền là ~w_{i, j} * s_i * s_j~.

Biết bạn có vô hạn lượt đổi dấu, tìm tổng tiền phạt nhỏ nhất bạn có thể thu được.

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \leq N \leq 17)~. Dòng tiếp theo gồm ~N~ số nguyên ~h_1, h_2, ..., h_N~ ~(-10^6 \leq h_i \leq 10^6)~. ~N - 1~ dòng tiếp theo, dòng thứ ~i~ gồm ~N - i~ số nguyên ~w_{i, i + 1}, w_{i, i + 2}, ..., w_{i, N}~ ~(-10^6 \leq w_{i, j} \leq 10^6)~.

Output

Một số nguyên duy nhất là giá trị nhỏ nhất của biểu thức.

Sample Input 1

2
10 10
21

Sample Output 1

-21

Sample Input 2

3
-3 -2 1
3 -3
-3

Sample Output 2

-7

Sample Input 3

4
-2 5 3 4
-4 -4 0
0 2
3

Sample Output 3

-15

Notes