/ 
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