قرر 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