AT_abc395_g [ABC395G] Minimum Steiner Tree 2

正整数 $ N,K $ が与えられます。また、 $ N\times N $ 行列 $ C=(C_{i,j}) $ $ (1\leq i,j\leq N) $ が与えられます。ここで、 $ C_{i,i}=0,C_{i,j}=C_{j,i} $ が保証されます。 頂点に $ 1,2,\dots,N $ と番号がつけられた $ N $ 頂点の重み付き完全グラフがあります。 $ i\lt j $ なる頂点の組 $ i,j $ について、頂点 $ i $ と頂点 $ j $ を結ぶ辺の重みは $ C_{i,j} $ です。 $ Q $ 個のクエリが与えられます。 $ i $ 番目のクエリでは $ K+1 $ 以上 $ N $ 以下の相異なる整数の組 $ s_i,t_i $ が与えられるので、以下の問題を解いてください。 > このグラフから $ 0 $ 個以上好きな個数辺と頂点を取り除いてできる**連結な**グラフのうち、頂点 $ 1,2,\dots,K,s_i,t_i $ をすべて含むようなものを**良いグラフ**とよびます。 > > 良いグラフの**コスト**を、グラフに含まれる辺の重みの総和とします。 > > 良いグラフのコストの最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ C_{1,1} $ $ C_{1,2} $ $ \dots $ $ C_{1,N} $ $ C_{2,1} $ $ C_{2,2} $ $ \dots $ $ C_{2,N} $ $ \vdots $ $ C_{N,1} $ $ C_{N,2} $ $ \dots $ $ C_{N,N} $ $ Q $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ $ \vdots $ $ s_Q $ $ t_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ i $ 番目の頂点と $ j $ 番目の頂点を結ぶ辺を辺 $ i-j $ と表記します。 $ 1 $ 番目のクエリについて、以下の頂点と辺を残しそれ以外を消すのが最適で、このときのグラフのコストは $ 4 $ です。 - 頂点 $ 1,2,3,4,5 $ - 辺 $ 1-4,2-3,3-5,4-5 $ $ 2 $ 番目のクエリについて、以下の頂点と辺を残しそれ以外を消すのが最適で、このときのグラフのコストは $ 3 $ です。 - 頂点 $ 1,2,3,5 $ - 辺 $ 1-5,2-3,3-5 $ ### Constraints - $ 3\leq N\leq 80 $ - $ 1\leq K\leq \min(N-2,\textcolor{red}{8}) $ - $ 0\leq C_{i,j}\leq 10^9 $ $ (1\leq i,j\leq N,i\ne j) $ - $ C_{i,j}=C_{j,i} $ $ (1\leq i,j\leq N,i\ne j) $ - $ C_{i,i}=0 $ $ (1\leq i\leq N) $ - $ 1\leq Q\leq 5000 $ - $ K+1\leq s_i,t_i\leq N $ $ (1\leq i\leq Q) $ - $ s_i\ne t_i $ $ (1\leq i\leq Q) $ - 入力はすべて整数