032 - AtCoder Ekiden(★3) Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 3

問題文

ABC 陸上部には N 人の駅伝選手がいます。駅伝では 1 人の選手が 1 つの区を担当して走ります。複数の選手が 1 つの区を担当することや 1 人の選手が複数の区を担当することはできません。駅伝コースは第 1 区から第 N 区まであり、選手 i が第 j 区を走るのにかかる時間は A_{i, j} です。

駅伝は第 1 区、第 2 区、……、第 N 区の順にその区間を担当する選手が走ります。第 j 区 (1 \leq j \leq N - 1) を走り終わった選手は第 j + 1 区を走る選手にタスキを渡さなければいけません。このとき、タスキの受け渡しにかかる時間は十分短いため無視できます。最後にタスキを受けとった選手が第 N 区を走りゴールとなります。

さて、ABC 陸上部には M 個の噂があります。i 番目の噂は「選手 X_i と選手 Y_i は仲が悪い」というものです。噂をされている選手同士ではタスキの受け渡しができません。つまり、選手 X_i の直後に選手 Y_i が走ることも選手 Y_i の直後に選手 X_i が走ることもできません。

ABC 陸上部が駅伝でゴールするまでにかかる時間の最小値を求めてください。ただし、各選手が走る区間をどのように決めてもゴールできない場合、代わりに -1 を出力してください。

制約

  • 1 \leq N \leq 10
  • 1 \leq A_{i, j} \leq 1000 \ (1 \leq i \leq N, 1 \leq j \leq N)
  • 0 \leq M \leq N(N - 1)/2
  • 1 \leq X_i < Y_i \leq N \ (1 \leq i \leq M)
  • (X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
  • 入力は全て整数

入力

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

N
A_{1, 1} A_{1, 2} \cdots A_{1, N}
A_{2, 1} A_{2, 2} \cdots A_{2, N}
\vdots
A_{N, 1} A_{N, 2} \cdots A_{N, N}
M
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

出力

ゴールするまでにかかる時間の最小値を出力してください。ただし、各選手が走る区間をどのように決めてもゴールできない場合 -1 を出力してください。


入力例 1

3
1 10 100
10 1 100
100 10 1
1
1 2

出力例 1

111

選手 1 が第 1 区を走り、選手 2 が第 3 区を走り、選手 3 が第 2 区を走ることで最小値 111 を達成できます。


入力例 2

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2
1 3
2 3

出力例 2

-1

入力例 3

3
1 10 100
10 1 100
100 10 1
0

出力例 3

3

Source Name

「競プロ典型90問」32日目