Problem
この国には N 個の都市があり、そのうちのいくつかは道路で結ばれています。 1 本の道路を走行するのに 1 タンクのガソリンが必要です。さらに、ガソリン タンクと同じ量の燃料を入れるガス キャニスターもあります。
各都市では、ガソリン タンクのコストが異なります。できるだけお金を使わずに、最初の都市から N 番目の都市まで移動する必要があります。
各都市では、タンクにガソリンを満タンにしたり、タンクとキャニスターにガソリンを入れたり、キャニスターからタンクにガソリンを注ぐことができます。これにより、ガソリンが安い都市でガソリンを購入してお金を節約できますが、キャニスターはタンク 1 回分しか充填できません。
入力
最初の行には数値 N (1<=N<=100) が含まれ、次の行には N 個の数値が含まれ、その i 番目の数値は i 番目の都市のガソリンのコストを設定します (これらはすべて次の整数です)範囲は 0 ～ 100 です）。次に M という数字が続きます –国内の道路の数、その後に道路自体の説明が続きます。各道路は 2 つの番号で指定されます –接続する都市の数。すべての道路は双方向です (つまり、一方向と反対方向の両方に運転できます)。2 つの都市の間には常に 1 本の道路しかなく、都市からその都市に通じる道路はありません。
出力
単一の数値を出力するために必要 –ルートの総コスト、またはそこに到達することが不可能な場合は -1。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |