• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

به تازگی اسنپ کار خود را گسترش داده‌است و علاوه بر ایران به مردم شکرستان هم سرویس می‌دهد. شکرستان به $N$ منطقه تقسیم شده است و هزینه سفر از منطقه $i$ به منطقه $j$ مقدار مشخصی است که آن را با $A_{ij}$ نشان می‌دهیم. (توجه کنید که ممکن است هزینه سفر از $i$ به $j$ با هزینه سفر از $j$ به $i$ متفاوت باشد.)

این ماه اسکندر $M$ سفر با اسنپ انجام داده‌است و حال میخواهد محاسبه کند که در مجموع چقدر هزینه این سفر‌ها شده است.

حال ما هزینه سفر از هر منطقه به مناطق دیگر و همچنین به ازای هر سفر اسکندر، مبدا و مقصد آن را به شما می‌دهیم. شما باید بگویید که خرج سفر‌های اسکندر در مجموع چقدر بوده است. البته از آنجایی که اسکندر اصلا آدم تنبلی نیست به شما این تضمین را می‌دهیم که به ازای هر سفر منطقه مبدا و منطقه مقصد آن متفاوت است.

برای فهم بهتر، بخش ورودی و توضیح ورودی‌ نمونه ۱ را بخوانید.

ورودی

ابتدا در یک سطر $N$ و $M$ که به ترتیب نمایانگر تعداد مناطق شکرستان و تعداد سفرهای اسکندر است، به شما داده می‌شود. سپس در $N$ سطر بعدی در هر خط $N$ عدد به شما داده می‌شود که عدد $j$ ام در سطر $i$ ام هزینه سفر از منطقه $i$ به منطقه $j$‌یا $A_{ij}$ است. سپس در $M$ سطر بعدی در هر سطر به شما دو عدد مانند $x_k$ و $y_k$ به شما داده می‌شود که به ترتیب نمایانگر مبدا و مقصد سفر $k$ ام اسکندر است. برای فهم بیشتر حتما توضیح نمونه ۱ را بخوانید. $$ 2 \le N \le 10$$ $$ 1 \le M \le 20$$ $$ 1 \le A_{ij} \le 1000$$ $$ 1 \le x_k , y_k \le N$$ $$ x_k \ne y_k$$

خروجی

در یک خط یک عدد چاپ کنید که نشان‌دهنده هزینه کل سفر‌های اسکندر است.

مثال

ورودی نمونه ۱

3 3
1 50 66
72 1 12
91 29 1
1 3
2 3
3 1

خروجی نمونه ۱

169

توضیح: با توجه به ورودی های سوال اسکندر ۳ سفر انجام داده است که هزینه سفر اول ۶۶ ، هزینه سفر دوم ۱۲ و هزینه سفر سوم ۹۱ شده است و در مجموع ۱۶۹ = ۹۱ + ۱۲ + ۶۶ پرداخت کرده است.

ورودی نمونه ۲

4 4
277 30 971 789
65 379 158 855
892 92 267 454
449 293 735 533
2 3
4 3
1 3
2 4

خروجی نمونه ۲

2719