라이언 동상 구하기
시간 제한3초메모리 제한1024 MB
N x N 정사각형의 각 변에서 정수 좌표 한 점씩을 골라 더 작은 직사각형을 만들고, 경계에 놓인 조각상을 포함해 덮는 조각상 가치 합의 최댓값을 구한다.
문제
Bryan에겐 정사각형 모양의 땅이 있다. 편의상 이 땅의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 각 변은 X축 또는 Y축과 평행하다고 하자.
이 땅 안에는 라이언 동상과 브라운 동상을 합쳐 M개의 동상이 있다. 땅의 테두리에는 울타리가 쳐져 있어서 동상은 놓여 있지 않다. 어느 날 bryan은 kazel이 자신의 땅을 습격하려 한다는 사실을 알게 되었다. kazel은 땅의 꼭짓점 위치에서 습격하기 때문에, bryan은 각 변에서 꼭짓점을 제외한 정수 좌표 위치에 기둥을 하나씩 세우고 그 기둥을 이어 새로운 사각형 울타리를 만들어 kazel의 습격으로부터 보호할 새로운 땅을 만들기로 결심했다.
Bryan은 각 동상에 Vi의 가치를 매기고, 새로운 땅에 포함되는 동상의 가치 합을 최대로 하려고 한다. 새로운 땅의 울타리 위에 있는 동상도 새로운 땅에 포함된다.
또한 kazel은 브라운 동상을 노리고 습격하기 때문에, kazel이 다시 습격할 위험을 줄이기 위해 브라운 동상은 새로운 땅에 최대한 포함되지 않도록 하려고 한다. 따라서 이 브라운 동상에는 양수가 아닌 가치가 매겨져 있다. (당연하지만 라이언 동상에는 양수의 가치가 매겨져 있다.)
Bryan은 새 울타리를 칠 재료를 준비하느라 바쁘기 때문에, 새로운 울타리를 어떻게 쳐야 하는지는 당신이 대신 계산해 주자.
입력
첫째 줄에 bryan이 처음 가진 땅의 한 변의 길이 N과 동상의 개수 M이 주어진다. 둘째 줄부터 M개 줄에 걸쳐 각 동상의 위치 Xi, Yi와 가치 Vi가 주어진다.
- 2 ≤ N ≤ 500
- 1 ≤ M ≤ 500
- 0 < Xi, Yi < N
- -10^5 ≤ Vi ≤ 10^5
출력
조건에 맞게 만든 새로운 땅에 포함된 동상들의 가치 합의 최댓값을 출력한다.