Snuke 正在构造一个长度为 $n$ 的整数序列 $x = (x_1,x_2,\cdots,x_n)$。对于每个 $1\le i \le n$，$x_i$ 都有 $m$ 个候选值，其中第 $k$ 个记作 $a_{i,k}$。选择 $a_{i,k}$ 需要花费 $c_{i,k}$。

此外，在确定序列 $x$ 后，对每对满足 $1\le i < j \le n$ 的 $(i,j)$ 还需要花费 $|x_i-x_j|\times W_{i,j}$。

请输出最小花费。

$2\le n\le 50,\ 2\le m \le 5,\ 1\le a_{i,1} < a_{i,2} < \cdots < a_{i,m} \le 10^6,\ 1\le c_{i,k} \le 10^{15},\ 1\le W_{i,j}\le 10^6$ 。