يبحر Farmer John بحثًا عن كنز أسطوري بإحدى جزر Cowribbean Sea وعددها $N$ $(1 \le N \le 100)$، مرقمة $1,\ldots,N$.

تطلب الخريطة بدءًا من1 ونهاية عند $N$، عبر تسلسل $A_{1}$ و$A_{2}$ و... و$A_{M}$ من $M$ جزر $(2 \le M \le 10,000)$ قبل ظهور الكنز. يمكن زيارتها وغيرها خارج الترتيب ومكررًا، لكن يجب أن تشمل الرحلة $A_{i}$ بالترتيب المحدد.

يريد FJ تجنب القراصنة ويعرف الخطر $(0 \le danger \le 100,000)$ بين كل زوج جزر. الإجمالي مجموع أخطار كل الطرق التي يقطعها.

جد أقل مسار خطرًا للكنز يلبي الخريطة.

الإدخال

• السطر1: عددان صحيحان بفاصل فراغ، $N$ و$M$.
• الأسطر $2,\ldots,M+1$: السطر $i+1$ يصف الجزيرة الإلزامية رقم $i_{th}$ بالعدد $A_{i}$.
• الأسطر $M+2,\ldots,N+M+1$: السطر $i+M+1$ فيه $N$ أعداد صحيحة بفاصل فراغ لأخطار المسارات من $i$ إلى1، 2، ...، $N$. العدد $i$ دائمًا صفر.

الإخراج

• السطر1: أقل خطر عند الحصول على الكنز.

أمثلة

الإدخال 1

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

الإخراج 1

7

ملاحظة

3 جزر و4 زيارات:1، 2، مجددًا1، أخيرًا3. طرق(1,2)، (2,3)، (3,1) وعكسها أخطارها5، 2، 1.

المسار1، 3، 2، 3، 1، 3 إجماليه7 ويحقق1، 2، 1، 3. نتجنب1–2 لارتفاع الخطر.

مؤلف المسألة: Jeffrey Wang, 2007