Nông dân John quyết định mang nước tới cho \(N\) đồng cỏ của mình, để thuận tiện ta đánh số các đồng cỏ từ \(1\) đến \(N\). Để tưới nước cho \(1\) đồng cỏ John có thể chọn \(2\) cách, \(1\) là đào ở đồng cỏ đó \(1\) cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tới.

Để đào một cái giếng ở đồng cỏ \(i\) cần \(1\) số tiền là \(W_{i}\). Lắp ống dẫn nước nối \(2\) đồng cỏ \(i\) và \(j\) cần một số tiền là \(P_{ij}\).

Tính xem nông dân John phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(N\) \((1 \leq N \leq 300)\) - số lượng đồng cỏ.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa 1 số nguyên duy nhất \(W_i\) \((1 \leq W_i \leq 100,000)\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên cách nhau bởi dấu cách, số thứ \(j\) là \(P_{ij}\) \((1 \leq P_{ij} \leq 10^{5}, P_{ij} = P_{ji}, P_{ii} = 0)\).

Output

• Một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.

Example

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

9