AT_abc395_g [ABC395G] Minimum Steiner Tree 2

You are given positive integers $ N, K $ , and an $ N \times N $ matrix $ C=(C_{i,j}) $ $ (1\leq i,j\leq N) $ . It is guaranteed that $ C_{i,i} = 0 $ and $ C_{i,j} = C_{j,i} $ . There is a weighted complete graph with $ N $ vertices labeled $ 1,2,\dots,N $ . For each pair of vertices $ i $ and $ j $ with $ i\lt j $ , the weight of the edge connecting vertices $ i $ and $ j $ is $ C_{i,j} $ . You have $ Q $ queries. In the $ i $ -th query, you are given a pair of distinct integers $ s_i $ and $ t_i $ (both between $ K+1 $ and $ N $ , inclusive), for which you must solve the following problem. > A **good graph** is a **connected** graph containing all of the vertices $ 1,2,\dots,K,s_i,t_i $ obtained by removing any number of edges and vertices (possibly zero) from the graph above. > > The **cost** of a good graph is the sum of the weights of its edges. > > Find the minimum possible cost of a good graph.

The input is given from Standard Input in the following format: > $ 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 $

Print $ Q $ lines. The $ i $ -th line should contain the answer for the $ i $ -th query.

### Sample Explanation 1 Let “edge $ i-j $ ” denote the edge connecting vertices $ i $ and $ j $ . For the first query, it is optimal to keep the following vertices and edges, and remove all others. The cost is $ 4 $ . - Vertices $ 1,2,3,4,5 $ - Edges $ 1-4,2-3,3-5,4-5 $ For the second query, it is optimal to keep the following vertices and edges, and remove all others. The cost is $ 3 $ . - Vertices $ 1,2,3,5 $ - Edges $ 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) $ - All input values are integers.