Problem
N شهر در کشور وجود دارد که برخی از آنها از طریق جاده به یکدیگر متصل هستند. رانندگی در یک جاده به یک باک بنزین نیاز دارد. علاوه بر این، شما یک کپسول گاز دارید که به اندازه یک مخزن بنزین سوخت را در خود جای می دهد.
در هر شهر یک باک بنزین هزینه متفاوتی دارد. شما باید از اولین شهر به شهر نهم بروید و تا حد امکان کمتر پول خرج کنید.
در هر شهر می توانید باک را پر کنید، باک و قوطی را پر کنید یا بنزین را از قوطی داخل باک بریزید. این به شما امکان می دهد با خرید بنزین در شهرهایی که ارزان تر است در هزینه خود صرفه جویی کنید، اما قوطی فقط برای یک بار پر کردن باک کافی است!
ورودی
خط اول شامل عدد N (1<=N<=100) است، سطر بعدی حاوی N عدد است که i-امین آن هزینه بنزین در شهر i را تعیین می کند (این اعداد صحیح از 0 هستند. تا 100). سپس عدد M – تعداد جاده های کشور و به دنبال آن شرحی از خود جاده ها. هر جاده با دو عدد داده می شود – تعداد شهرهایی که به آن متصل است. همه راه ها دو طرفه هستند (یعنی می توان آنها را هم در یک جهت و هم در جهت دیگر راند)، همیشه بین دو شهر یک جاده بیشتر نیست، هیچ جاده ای از شهر به سمت خودش منتهی نمی شود. div>
خروجی
برای خروجی یک عدد مورد نیاز است – هزینه کل مسیر، یا -1 اگر رسیدن به آنجا غیرممکن است.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |