AT_arc129_e [ARC129E] Yet Another Minimization

すぬけ君想要构造一个长度为 $N$ 的整数序列 $x=(x_1,x_2,\cdots,x_N)$。对于每个 $i$（$1 \leq i \leq N$），$x_i$ 有 $M$ 种可选值，其中第 $k$ 种值为 $A_{i,k}$。选择 $A_{i,k}$ 时，需要花费 $C_{i,k}$ 的代价。 此外，确定 $x$ 之后，对于每一对 $i,j$（$1 \leq i < j \leq N$），还需要额外支付 $|x_i-x_j| \times W_{i,j}$ 的代价。 请你求出所有可能的总代价的最小值。

输入按以下格式从标准输入读入。 > $N$ $M$ $A_{1,1}$ $C_{1,1}$ $A_{1,2}$ $C_{1,2}$ $\cdots$ $A_{1,M}$ $C_{1,M}$ $A_{2,1}$ $C_{2,1}$ $A_{2,2}$ $C_{2,2}$ $\cdots$ $A_{2,M}$ $C_{2,M}$ $\cdots$ $A_{N,1}$ $C_{N,1}$ $A_{N,2}$ $C_{N,2}$ $\cdots$ $A_{N,M}$ $C_{N,M}$ $W_{1,2}$ $W_{1,3}$ $\cdots$ $W_{1,N-1}$ $W_{1,N}$ $W_{2,3}$ $W_{2,4}$ $\cdots$ $W_{2,N}$ $\cdots$ $W_{N-1,N}$

请输出答案。

### 限制条件 - $2 \leq N \leq 50$ - $2 \leq M \leq 5$ - $1 \leq A_{i,1} < A_{i,2} < \cdots < A_{i,M} \leq 10^6$ - $1 \leq C_{i,k} \leq 10^{15}$ - $1 \leq W_{i,j} \leq 10^6$ - 所有输入的值均为整数 ### 样例解释 1 如果选择 $x=(5,9,7)$，各项代价如下： - $x_1$ 选择 $A_{1,2}$，代价为 $C_{1,2}=2$。 - $x_2$ 选择 $A_{2,2}$，代价为 $C_{2,2}=4$。 - $x_3$ 选择 $A_{3,1}$，代价为 $C_{3,1}=2$。 - 对于 $(i,j)=(1,2)$，代价为 $|x_i-x_j| \times W_{i,j}=4$。 - 对于 $(i,j)=(1,3)$，代价为 $|x_i-x_j| \times W_{i,j}=10$。 - 对于 $(i,j)=(2,3)$，代价为 $|x_i-x_j| \times W_{i,j}=6$。 由 ChatGPT 4.1 翻译