Farmer John מספק מים ל־$N$ שטחי מרעה ($1 \le N \le 300$), ממוספרים $1,\ldots,N$. אפשר לבנות באר בשטח או לחבר בצינור לשטח אחר שכבר יש בו מים.

באר ב־$i$ עולה $W_i$ ($1 \le W_i \le 100,000$). צינור בין $i$, $j$ עולה $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

מצאו את העלות המזערית לספק מים לכולם.

קלט

• שורה 1: השלם $N$.
• שורות $2,\ldots,N+1$: שורה $i+1$ מכילה את השלם $W_i$.
• שורות $N+2,\ldots,2N+1$: שורה $N+1+i$ מכילה $N$ שלמים מופרדים ברווחים; ה־$j$ הוא $P_{ij}$.

פלט

• שורה 1: מספר שלם, עלות מזערית לאספקת מים לכל השטחים.

דוגמאות

קלט 1

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

פלט 1

9

הערה

ארבעה שטחים: באר ב־1 עולה 5, ב־2 ו־3 עולה 4, ב־4 עולה 3. צינורות עולים 2, 3, 4 לפי השטחים.

באר ב־4 וחיבור כל שטח ל־1 עולים $3+2+2+2=9$.

תתי־משימות

נקודות: 400

מחבר הבעיה: Paul Christiano, 2007