Farmer John cấp nước cho $N$ đồng cỏ ($1 \le N \le 300$), đánh số $1,\ldots,N$. Có thể đào giếng tại đồng đó hoặc nối ống tới đồng khác đã có nước.

Giếng ở $i$ giá $W_i$ ($1 \le W_i \le 100,000$). Ống nối $i$, $j$ giá $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Tìm giá thấp nhất cấp nước cho tất cả.

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Các dòng $2,\ldots,N+1$: dòng $i+1$ chứa số nguyên $W_i$.
• Các dòng $N+2,\ldots,2N+1$: dòng $N+1+i$ chứa $N$ số nguyên cách nhau bởi dấu cách; số thứ $j$ là $P_{ij}$.

Dữ liệu ra

• Dòng 1: số nguyên, giá thấp nhất cấp nước cho mọi đồng.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

9

Ghi chú

Bốn đồng: giếng ở 1 giá 5, ở 2 và 3 giá 4, ở 4 giá 3. Ống giá 2, 3, 4 tùy đồng nối.

Giếng ở 4 và nối mỗi đồng với 1 giá $3+2+2+2=9$.

Nhiệm vụ con

Điểm: 400

Tác giả: Paul Christiano, 2007