燃やす埋める練習問題3

2 secs 1024 MB
_kanpurin_'s icon _kanpurin_

問題文

NN人の人が数直線上に家を建てようとしています。ii番目の人が建てる家の場所の候補はMM個あり、このうちちょうど11つの地点を選び家を建てます。jj番目の候補は地点Pi,jP_{i,j}にあり、この地点に家を建てると不満度がAi,jA_{i,j}増えます。また、友達関係にある人のペアがKK組与えられ、kk番目のペアであるxkx_k番目の人とyky_k番目の人が建てた家の距離がDDである場合、不満度がBk×D2B_{k}\times D^2増えます。

NN人の家の場所を適切に決めることで不満度の和を最小化してください。

制約

  • 2N1002 \leq N \leq 100
  • 2M52 \leq M \leq 5
  • 1Kmin(N(N1)/2,400)1 \leq K \leq \min(N(N-1)/2,400)
  • 0Pi,1<Pi,2<<Pi,M1030 \leq P_{i,1} < P_{i,2} < \dots < P_{i,M} \leq 10^3
  • 109Ai,j109-10^9 \leq A_{i,j} \leq 10^9
  • 1xk<ykN1 \leq x_{k} < y_{k} \leq N
  • 0Bk1090 \leq B_{k} \leq 10^9

入力

入力はすべて整数である。

N M KN\ M\ K
P1,1 P1,2  P1,MP_{1,1}\ P_{1,2}\ \dots\ P_{1,M}
P2,1 P2,2  P2,MP_{2,1}\ P_{2,2}\ \dots\ P_{2,M}
\vdots
PN,1 PN,2  PN,MP_{N,1}\ P_{N,2}\ \dots\ P_{N,M}
A1,1 A1,2  A1,MA_{1,1}\ A_{1,2}\ \dots\ A_{1,M}
A2,1 A2,2  A2,MA_{2,1}\ A_{2,2}\ \dots\ A_{2,M}
\vdots
AN,1 AN,2  AN,MA_{N,1}\ A_{N,2}\ \dots\ A_{N,M}
x1 y1 B1x_1\ y_1\ B_1
x2 y2 B2x_2\ y_2\ B_2
::
xK yK BKx_K\ y_K\ B_K

出力

不満度の最小値を一行に出力せよ。

サンプル

入力1
2 2 1
1 3
3 4
2 5
6 3
1 2 4
出力1
11

11番目の人が建てる家の場所の候補は{1,3}\{1,3\}22番目の人が建てる家の場所の候補は{3,4}\{3,4\}です。22人とも地点33に家を建てると不満度は合計で1111になります。

入力2
2 3 1
1 5 9
2 4 7
-4 4 8
-1 9 8
1 2 1
出力2
-4

11番目の人は地点11に、22番目の人は地点22に家を建てるのが最適です。不満度が負になる場合もあります。

提出


Go (1.21)