Problem
Terdapat N bandar di negara ini, sebahagian daripadanya disambungkan melalui jalan raya. Ia memerlukan satu tangki petrol untuk memandu di satu jalan. Selain itu, anda mempunyai tong gas yang menyimpan jumlah bahan api yang sama dengan tangki gas.
Di setiap bandar, satu tangki petrol mempunyai kos yang berbeza. Anda perlu pergi dari bandar pertama ke bandar Nth, membelanjakan wang sesedikit mungkin.
Di setiap bandar, anda boleh mengisi tangki, mengisi tangki dan tong, atau menuang petrol dari tong ke dalam tangki. Ini membolehkan anda menjimatkan wang dengan membeli petrol di bandar yang harganya lebih murah, tetapi kanister hanya cukup untuk mengisi satu tangki!
Input
Baris pertama mengandungi nombor N (1<=N<=100), baris seterusnya mengandungi nombor N, ke-i yang menetapkan kos petrol di bandar ke-i (semua ini adalah integer dari julat dari 0 hingga 100). Kemudian datang nombor M – bilangan jalan di negara ini, diikuti dengan penerangan jalan itu sendiri. Setiap jalan diberi dua nombor – bilangan bandar yang disambungkannya. Semua jalan adalah dua hala (iaitu, ia boleh dipandu kedua-duanya dalam satu arah dan ke arah yang lain), sentiasa ada tidak lebih daripada satu jalan antara dua bandar, tidak ada jalan yang menghala dari bandar ke sendiri.
Output
Diperlukan untuk mengeluarkan satu nombor – jumlah kos laluan, atau -1 jika mustahil untuk sampai ke sana.
Contoh
| # |
Input |
Output |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |