Catfish Farm

문제

Bu Dengklek owns a catfish farm. The catfish farm is a pond consisting of a $N\times NN\; \backslash times\; N$ grid of cells. Each cell is a square of the same size. The columns of the grid are numbered from $00$ to $N-1N\; -\; 1$ from west to east and the rows are numbered from $00$ to $N-1N\; -\; 1$ from south to north. We refer to the cell located at column $cc$ and row $rr$ of the grid ($0\le c\le N-10\; \backslash le\; c\; \backslash le\; N\; -\; 1$, $0\le r\le N-10\; \backslash le\; r\; \backslash le\; N\; -\; 1$) as cell $(c,r)(c,\; r)$.

In the pond, there are $MM$ catfish, numbered from $00$ to $M-1M\; -\; 1$, located at distinct cells. For each $ii$ such that $0\le i\le M-10\; \backslash le\; i\; \backslash le\; M\; -\; 1$, catfish $ii$ is located at cell $(X[i],Y[i])(X[i],\; Y[i])$, and weighs $W[i]W[i]$ grams.

Bu Dengklek wants to build some piers to catch the catfish. A pier in column $cc$ of length $kk$ (for any $0\le c\le N-10\; \backslash le\; c\; \backslash le\; N\; -\; 1$ and $1\le k\le N1\; \backslash le\; k\; \backslash le\; N$) is a rectangle extending from row $00$ to row $k-1k\; -\; 1$, covering cells $(c,0),(c,1),\dots ,(c,k-1)(c,\; 0),\; (c,\; 1),\; \backslash ldots,\; (c,\; k\; -\; 1)$. For each column, Bu Dengklek can choose either to build a pier of some length of her choice or to not build a pier.

Catfish $ii$ (for each $ii$ such that $0\le i\le M-10\; \backslash le\; i\; \backslash le\; M\; -\; 1$) can be caught if there is a pier directly to the west or east of it, and there is no pier covering its cell; that is, if

• at least one of the cells $(X[i]-1,Y[i])(X[i]\; -\; 1,\; Y[i])$ or $(X[i]+1,Y[i])(X[i]\; +\; 1,\; Y[i])$ is covered by a pier, and
• there is no pier covering cell $(X[i],Y[i])(X[i],\; Y[i])$.

For example, consider a pond of size $N=5N\; =\; 5$ with $M=4M\; =\; 4$ catfish:

• Catfish $00$ is located at cell $(0,2)(0,\; 2)$ and weighs $55$ grams.
• Catfish $11$ is located at cell $(1,1)(1,\; 1)$ and weighs $22$ grams.
• Catfish $22$ is located at cell $(4,4)(4,\; 4)$ and weighs $11$ gram.
• Catfish $33$ is located at cell $(3,3)(3,\; 3)$ and weighs $33$ grams.

One way Bu Dengklek can build the piers is as follows:

Before the piers are built	After the piers are built

The number at a cell denotes the weight of the catfish located at the cell. The shaded cells are covered by piers. In this case, catfish $00$ (at cell $(0,2)(0,\; 2)$) and catfish $33$ (at cell $(3,3)(3,\; 3)$) can be caught. Catfish $11$ (at cell $(1,1)(1,\; 1)$) cannot be caught, as there is a pier covering its location, while catfish $22$ (at cell $(4,4)(4,\; 4)$) can not be caught as there is no pier directly to the west nor east of it.

Bu Dengklek would like to build piers so that the total weight of catfish she can catch is as large as possible. Your task is to find the maximum total weight of catfish that Bu Dengklek can catch after building piers.