31227번 - 별 보러 가자

문제

천문학자 수연이는 $N$일 동안 총 $M$개의 별을 관측하였고, 각 별의 좌표를 관측한 순서대로 기록하였다. 밤하늘을 2차원 좌표평면으로 이해할 때, 별은 좌표평면상의 한 점으로 표현할 수 있다.

수연이가 어떤 날 관측한 별들의 대푯값 $R$은 그날 관측한 별 중 가장 멀리 떨어진 두 별 사이의 거리다. 이때, 두 별의 좌표가 각각 $(a,b),ドル $(c,d)$라면 두 별의 거리는 $|a-c|+|b-d|$이다. 만약 어떤 날 수연이가 관측한 4ドル$개의 별의 좌표가 순서대로 $(1,3),ドル $(6,-3),ドル $(-1,5),ドル $(5,4)$라면, 그날의 대푯값은 $R=|6-(-1)|+|-3-5|=15$이다. 관측한 별이 1ドル$개인 날의 경우 대푯값이 0ドル$임에 유의하자.

수연이는 매일 하나 이상의 별들을 관측한 것은 기억하지만, 정확히 어느 날에 어떤 별을 관측하였는지는 잊었다. 어차피 기억도 안 나는 거, 수연이는 별의 관측 순서를 유지하면서, 매일 하나 이상의 별을 관측했다는 사실을 바탕으로 $N$일간의 대푯값의 합이 최대가 되도록 별들의 관측 날짜를 적절히 구분하고 싶어졌다.

예를 들어 3ドル$일 동안 관측한 5ドル$개의 별의 좌표가 순서대로 $[p_{1},p_{2},\dots , p_{5}]$일 때, $[p_{1},p_{2}],[p_{3}],[p_{4},p_{5}]$와 같이 별들의 관측 날짜를 구분할 수 있지만 $[p_{1},p_{3}],[p_{2}],[p_{4},p_{5}]$나 $[p_{1},p_{2}],[p_{3},p_{4},p_{5}]$와 같이 구분할 수는 없다.

수연이가 관측한 별들의 관측 날짜를 적절히 구분한 뒤 $i$번째 날의 대푯값을 $R_{i}$라고 할 때, $\sum_{i=1}^{N}R_{i}$의 최댓값을 구하시오.

입력

첫째 줄에 수연이가 별을 관측한 날의 수 $N$과 관측한 별의 수 $M$이 공백으로 구분되어 주어진다. $(1\leq N\leq M\leq 3,000円)$

둘째 줄부터 $M$개의 줄에 걸쳐 수연이가 관측한 별의 $x$좌표와 $y$좌표가 공백으로 구분되어 주어진다. $\left(-10^{9}\leq x, y\leq 10^{9}\right)$

입력으로 주어지는 모든 값은 정수다.

출력

첫째 줄에 문제의 조건에 맞게 별들의 관측 날짜를 구분하였을 때 $\sum_{i=1}^{N}R_{i}$의 최댓값을 출력한다.

제한

힌트