燃やす埋める練習問題３

人の人が数直線上に家を建てようとしています。番目の人が建てる家の場所の候補は個あり、このうちちょうどつの地点を選び家を建てます。番目の候補は地点にあり、この地点に家を建てると不満度が増えます。また、友達関係にある人のペアが組与えられ、番目のペアである番目の人と番目の人が建てた家の距離がである場合、不満度が増えます。

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

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

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

2 2 1
1 3
3 4
2 5
6 3
1 2 4

11

番目の人が建てる家の場所の候補は、番目の人が建てる家の場所の候補はです。人とも地点に家を建てると不満度は合計でになります。

2 3 1
1 5 9
2 4 7
-4 4 8
-1 9 8
1 2 1

-4

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