{"problem":{"name":"Yet Another Minimization","description":{"content":"Snuke is making an integer sequence of length $N$: $x=(x_1,x_2,\\cdots,x_N)$. For each $i$ ($1 \\leq i \\leq N$), there are $M$ candidates for the value of $x_i$: the $k$\\-th of them is $A_{i,k}$. Choosi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc129_e"},"statements":[{"statement_type":"Markdown","content":"Snuke is making an integer sequence of length $N$: $x=(x_1,x_2,\\cdots,x_N)$. For each $i$ ($1 \\leq i \\leq N$), there are $M$ candidates for the value of $x_i$: the $k$\\-th of them is $A_{i,k}$. Choosing $A_{i,k}$ incurs a cost of $C_{i,k}$.\nAdditionally, after deciding $x$, a cost of $|x_i-x_j| \\times W_{i,j}$ is incurred for each $i,j$ ($1 \\leq i < j \\leq N$).\nFind the minimum possible total cost incurred.\n\n## Constraints\n\n*   $2 \\leq N \\leq 50$\n*   $2 \\leq M \\leq 5$\n*   $1 \\leq A_{i,1} < A_{i,2} < \\cdots < A_{i,M} \\leq 10^6$\n*   $1 \\leq C_{i,k} \\leq 10^{15}$\n*   $1 \\leq W_{i,j} \\leq 10^6$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_{1,1}$ $C_{1,1}$\n$A_{1,2}$ $C_{1,2}$\n$\\vdots$\n$A_{1,M}$ $C_{1,M}$\n$A_{2,1}$ $C_{2,1}$\n$A_{2,2}$ $C_{2,2}$\n$\\vdots$\n$A_{2,M}$ $C_{2,M}$\n$\\vdots$\n$A_{N,1}$ $C_{N,1}$\n$A_{N,2}$ $C_{N,2}$\n$\\vdots$\n$A_{N,M}$ $C_{N,M}$\n$W_{1,2}$ $W_{1,3}$ $\\cdots$ $W_{1,N-1}$ $W_{1,N}$\n$W_{2,3}$ $W_{2,4}$ $\\cdots$ $W_{2,N}$\n$\\vdots$\n$W_{N-1,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc129_e","tags":[],"sample_group":[["3 2\n1 1\n5 2\n2 3\n9 4\n7 2\n8 2\n1 5\n3","28\n\nAn optimal choice is $x=(5,9,7)$. The individual costs incurred here are as follows.\n\n*   Choosing $A_{1,2}$ for $x_1$ incurs a cost of $C_{1,2}=2$.\n*   Choosing $A_{2,2}$ for $x_2$ incurs a cost of $C_{2,2}=4$.\n*   Choosing $A_{3,1}$ for $x_3$ incurs a cost of $C_{3,1}=2$.．\n*   For $(i,j)=(1,2)$, a cost of $|x_i-x_j| \\times W_{i,j}=4$ is incurred.\n*   For $(i,j)=(1,3)$, a cost of $|x_i-x_j| \\times W_{i,j}=10$ is incurred.\n*   For $(i,j)=(2,3)$, a cost of $|x_i-x_j| \\times W_{i,j}=6$ is incurred."],["10 3\n19 2517\n38 785\n43 3611\n3 681\n20 758\n45 4745\n6 913\n7 2212\n22 536\n4 685\n27 148\n36 2283\n25 3304\n36 1855\n43 2747\n11 1976\n32 4973\n43 3964\n3 4242\n16 4750\n50 24\n4 4231\n22 1526\n31 2152\n15 2888\n28 2249\n49 2208\n31 3127\n40 3221\n47 4671\n24 6 16 47 42 50 35 43 47\n29 18 28 24 27 25 33 12\n5 43 20 9 39 46 30\n40 24 34 5 30 21\n50 6 21 36 5\n50 16 13 13\n2 40 15\n25 48\n20","27790"],["2 2\n1 1\n10 10\n1 1\n10 10\n100","2"]],"created_at":"2026-03-03 11:01:14"}}