F - RPG

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

カトーくんは、とあるRPGのシナリオを作っています。 このRPGでは \(N\) 個の場面があり、各場面は既に「戦闘」か「空き地」のどちらかであると決まっています。 また、 \(M\) 個の場面間をつなぐ移動通路があり、\(i\) 番目の通路は、場面 \(a_i\) から 場面 \(b_i\) へ移動が可能です。 最初、RPGの主人公であるシンヤくんは、場面 \(1\) にいて、自由に通路を移動し、場面 \(N\) に到達したらゲームクリアです。

シンヤくんには「元気」と「疲労」の2種類の状態があります。 「元気」状態では戦闘に挑むことができますが、「疲労」状態では戦闘することができません。 「疲労」状態で「戦闘」場面に到達するとゲームオーバーとなります。

シンヤくんは「元気」状態でゲームを開始します。 「戦闘」場面を通過すると、疲れて「疲労」状態になります。 「疲労」状態から「元気」状態に戻るためには「回復所」を通過する必要があります。

「回復所」は任意の「空き地」場面に設置することができます。 場面 \(i \ (2 \leq i \leq N-1)\) に回復所を設置するコストは \(c_i\) です。

現在、「回復所」をどこに設置するかは決まっていません。 そこでカトーくんは、以下の条件を満たすように、「回復所」を設置することにしました。

  • 場面 \(1\) から動き始めたシンヤくんが場面 \(N\)に向かうどのような移動を選んでも、任意の「戦闘」場面から他の「戦闘」場面に達する間に、少なくとも1回は「回復所」を通過する。
  • ゲームクリア時のシンヤくんの状態は「疲労」でも「元気」でもよい。

以上の条件を満たすようにカトーくんが「回復所」を設置する際に必要なコストの合計の最小値を求めてください。 どのように「回復所」を設置しても条件を満たすことができなければ、 -1 を出力してください。

制約

  • \(3 \leq N \leq 500\)
  • \(N-1 \leq M \leq 1000\)
  • \(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\)
    • \(c_i = -1\) ならば、場面 \(i\) は「戦闘」場面である。
    • \(c_i \geq 0\)ならば、場面 \(i\) は「空き地」場面であり、そこに「休憩所」を設置するコストは \(c_i\) である。
  • \(1 \leq a_i , b_i \leq N \ (1 \leq i \leq M)\)
    • 場面 \(a_i\) から、場面 \(b_i\) への移動通路があることを示す。
  • \(N\) 頂点 \(M\) 辺の有向グラフとみたとき、全ての頂点に対し、頂点 \(1\) からのパスと、頂点 \(N\) へ向かうパスが存在する。また、閉路は存在しない。
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\) \(M\)
\(c_2\) \(c_3\) \(\dots\) \(c_{N-1}\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

出力

条件を満たすような「回復所」の設置コストの合計の最小値を出力してください。 条件を満たすことができない場合は、 -1 を出力してください。


入力例 1

7 7
-1 100 10 1 -1
1 2
2 3
3 6
2 4
4 5
5 6
6 7

出力例 1

101

場面 \(3\) と場面 \(5\) を選ぶのが最適です。


入力例 2

4 3
-1 -1
1 2
2 3
3 4

出力例 2

-1

場面 \(2\) から場面 \(3\) の間に「休憩所」を設置することができません。