17447번 - 라이언 동상 구하기

Bryan에겐 정사각형 모양의 예쁜 땅이 있다. 편의상 이 땅의 왼쪽 아래 꼭짓점은 (0, 0) 위치에 놓여 있고, 각 변은 X축 또는 Y축 중 하나와 평행하다고 하자.

이 땅 안에는 라이언 동상과 브라운 동상을 합쳐 M개의 동상이 존재한다. 이 땅의 테두리에는 울타리가 쳐져 있기 때문에 동상은 놓여 있지 않다. 어느 날, bryan은 kazel이 자신의 땅을 습격하려 한다는 사실을 알게 되었다! kazel은 땅의 꼭짓점 위치에서 습격을 하기 때문에, bryan은 각 변에서 꼭짓점을 제외한 정수 좌표 위치에 기둥을 하나씩 세우고 그 기둥을 이어 새로운 사각형 울타리를 만들어서 kazel의 습격으로부터 보호할 새로운 땅을 만들기로 결심하였다.

Bryan은 각각의 동상에 V_i의 가치를 매기고, 새로운 땅에 포함되는 동상의 가치를 최대로 하기로 하였다. 새로운 땅의 울타리 위에 있는 동상 또한 새로운 땅에 포함된다.

또한 kazel은 브라운 동상을 노리고 습격을 하기 때문에, 아쉽지만 kazel이 다시 습격할 위험성을 줄이기 위해 브라운 동상은 새로운 땅에 최대한 포함되지 않도록 하려고 한다. 따라서 이 브라운 동상들에는 양수가 아닌 수의 가치가 매겨져 있다. (당연하지만 라이언 동상에는 양수의 가치가 매겨져 있다.)

Bryan은 새 울타리를 칠 재료를 준비하느라 바쁘기 때문에, 새로운 울타리를 어떻게 쳐야 하는지는 당신이 대신해서 계산해 주도록 하자.

첫째 줄에 bryan이 처음 가진 땅의 한 변의 길이 N과 동상의 개수 M이 주어진다. 두 번째 줄부터 M개 줄에 걸쳐서 각 동상의 위치 X_i, Y_i와 가치 V_i가 주어진다.

• 2 ≤ N ≤ 500
• 1 ≤ M ≤ 500
• 0 < X_i, Y_i < N
• -10⁵ ≤ V_i ≤ 10⁵

조건에 맞게 만든 새로운 땅에 포함된 동상들의 가치의 합의 최댓값을 출력한다.