解法
最初は端にコマを置いていけばいい、と思ったのですが全然違いました。
ある座標の周辺に、目標の座標が密集していると、この通りにはいきません（そもそもサンプル1でこの解法は落ちます)。
そこで、どうするかというと、目標の座標の差を上手く利用します。
個のコマそれぞれに、区間をうまく割り当てて、その範囲にある
をカバーしてもらうことを考えます。
すると、それぞれのコマの区間同士の差ができるだけ広くなればよいわけです。
コマが
をカバー、
が
をカバーするとし、
の方が値が小さいとします。すると、
はどちらのコマもカバーしない場所になります。ここに、目標の
が入らないようにうまく区間を作成したとき、求める値は結局次のようになります。
を降順でソートし、一番大きい値から一番小さい値を引く(
とします)。その後、
の隣り合った座標の差を
個すべて求め、それをまた降順にソートする。その後、大きい方から
個取り出し、
から引く。
で、最終的に出てきた値が求める答えになります。
個コマがあるので、その間にある区間は
個になります。その区間を、大きい方から順番に選んでいけば、目標の値をどんどん小さいものにできます。
のときは、問答無用で答えが0になることに注意してください。REを吐く可能性が出てきます。
