cho.sh

메기 농장

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

부 뎅클렉은 메기 양어장을 가지고 있다. 양어장은 N×NN \times N 격자칸 모양이다. 격자의 칸들은 같은 크기의 정사각형이다. 격자의 열들은 서쪽에서 동쪽으로 00부터 N−1N - 1까지 번호가 붙어 있고, 행들은 남쪽에서 북쪽으로 00부터 N−1N - 1까지 번호가 붙어있다. 열 cc, 행 rr에 (0≤c≤N−10 \le c \le N - 1, 0≤r≤N−10 \le r \le N - 1) 있는 칸을 칸 (c,r)(c, r)로 부른다.

양어장에는 MM 마리의 메기가 있다. 메기들은 00부터 M−1M - 1까지 번호가 붙어 있고, 모두 다른 칸에 있다. 각각의 ii에 대해 (0≤i≤M−10 \le i \le M - 1) 메기 ii는 칸 (X\[i],Y\[i])(X\[i], Y\[i])에 있고, 그 무게는 W\[i]W\[i]그램이다.

부 뎅클렉은 메기를 잡기 위해 낚시터를 지으려고 한다. 열 cc에 있는 길이 kk인 낚시터는 (0≤c≤N−10 \le c \le N - 1, 1≤k≤N1 \le k \le N), 열 cc의 행 00부터 행k−1k - 1까지를 덮는 직사각형이다. 즉, 낚시터는 칸들 (c,0),(c,1),…,(c,k−1)(c, 0), (c, 1), \ldots, (c, k - 1)를 덮는다. 각 열에 대해서 부 뎅클렉은 특정한 길이의 낚시터를 짓거나, 낚시터를 전혀 짓지 않는 것 중 선택을 할 수 있다.

메기 ii를 (0≤i≤M−10 \le i \le M - 1) 잡기 위해서는 메기 ii의 위치의 서쪽이나 동쪽에 인접한 칸을 낚시터가 덮어야 하며, 메기 ii의 위치는 낚시터가 덮지 않아야 한다. 다시 말하면,

  • 칸들 (X\[i]−1,Y\[i])(X\[i] - 1, Y\[i])와 (X\[i]+1,Y\[i])(X\[i] + 1, Y\[i]) 중 적어도 하나가 낚시터에 덮이고,
  • 칸 (X\[i],Y\[i])(X\[i], Y\[i])는 낚시터에 덮이지 않아야 한다.

예를 들어, N=5N = 5인 양어장에 M=4M = 4마리의 메기가 있다고 하자.

  • 메기 00의 위치는 칸 (0,2)(0, 2)이고 그 무게는 55그램이다.
  • 메기 11의 위치는 칸 (1,1)(1, 1)이고 그 무게는 22그램이다.
  • 메기 22의 위치는 칸 (4,4)(4, 4)이고 그 무게는 11그램이다.
  • 메기 33의 위치는 칸 (3,3)(3, 3)이고 그 무게는 33그램이다.

부 뎅클렉이 낚시터를 지을 수 있는 방법 중 하나는 아래와 같다.

낚시터 짓기 전낚시터 지은 후

칸에 표시된 자연수는 그 칸에 있는 메기의 무게이다. 색칠된 칸들이 낚시터에 덮인 곳이다. 이 경우 잡을 수 있는 메기는 메기 00(칸 (0,2)(0, 2)에 위치)과 메기 33(칸 (3,3)(3, 3)에 위치)이다. 메기 11(칸 (1,1)(1, 1)에 위치)는 그 칸이 낚시터에 덮여 있어 잡을 수 없다. 메기 22(칸 (4,4)(4, 4)에 위치)는 서쪽이나 동쪽에 인접한 칸이 낚시터로 덮인 것이 없어 잡을 수 없다.

부 뎅클렉은 잡을 수 있는 메기의 무게의 합이 가장 크도록 낚시터를 짓고 싶다. 잡을 수 있는 메기의 최대 무게 합을 계산하는 프로그램을 작성하라.

제한

  • 2≤N≤100,0002 \le N \le 100\\,000
  • 1≤M≤300,0001 \le M \le 300\\,000
  • 0≤X\[i]≤N−10 \le X\[i] \le N - 1, 0≤Y\[i]≤N−10 \le Y\[i] \le N - 1 (0≤i≤M−10 \le i \le M - 1)
  • 1≤W\[i]≤1091 \le W\[i] \le 10^9 (0≤i≤M−10 \le i \le M - 1)
  • 메기들의 위치는 모두 다르다. 즉, X\[i]≠X\[j]X\[i] \neq X\[j] 혹은 Y\[i]≠Y\[j]Y\[i] \neq Y\[j] (0≤i<j≤M−10 \le i \lt j \le M - 1).