P8490 [IOI 2022] 鲶鱼塘
题目背景
# 滥用评测资源者封号
### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。
这是一道交互题，你只需要实现代码中要求的函数。
你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。
原题时间限制 1s，为了节约评测资源，时间限制修改为 0.5s。
题目描述
Bu Dengklek 有一个鲶鱼塘。这个鲶鱼塘是由 $N \times N$ 个网格单元构成的池塘。每个单元都是相同大小的正方形。网格各列自西向东编号为从 $0$ 到 $N - 1$，各行自南向北编号为从 $0$ 到 $N - 1$。我们把坐落在网格第 $c$ 列第 $r$ 行处（$0 \le c \le N - 1$，$0 \le r \le N - 1$）的单元记为单元 $(c, r)$。
池塘里总共有 $M$ 条鲶鱼，编号为从 $0$ 到 $M - 1$，分别位于**不同的**单元中。对每个满足 $0 \le i \le M - 1$ 的 $i$，鲶鱼 $i$ 在单元 $(X_i, Y_i)$ 中，其重量为 $W_i$ 克。
Bu Dengklek 想造些长堤来抓鲶鱼。在第 $c$ 列中长度为 $k$ 的长堤（对于所有 $0 \le c \le N - 1$ 和 $1 \le k \le N$），是一个从第 $0$ 行跨到第 $k - 1$ 行的矩形，盖住单元 $(c, 0), (c, 1), \ldots, (c, k - 1)$。对于每一列，Bu Dengklek 可以按照她自己选择的某个长度造长堤，也可以不造。
鲶鱼 $i$（对所有满足 $0 \le i \le M - 1$ 的 $i$）能被抓住，如果有某个长堤紧邻它的西侧或东侧，而且没有长堤盖住它所在的单元；也就是说，如果
* 单元 $(X_i - 1, Y_i)$ 或 $(X_i + 1, Y_i)$ 中 **至少有一个** 被某个长堤盖住，而且
* 没有长堤盖住单元 $(X_i, Y_i)$。
例如，考虑尺寸为 $N = 5$，有 $M = 4$ 条鲶鱼的池塘：
* 鲶鱼 $0$ 在单元 $(0, 2)$ 中，重量为 $5$ 克。
* 鲶鱼 $1$ 在单元 $(1, 1)$ 中，重量为 $2$ 克。
* 鲶鱼 $2$ 在单元 $(4, 4)$ 中，重量为 $1$ 克。
* 鲶鱼 $3$ 在单元 $(3, 3)$ 中，重量为 $3$ 克。
Bu Dengklek 可以这样来造长堤：
| 造长堤前 | 造长堤后 |
| :---: | :---: |
|  |  |
单元中的数字表示该单元中鲶鱼的重量。
阴影单元被长堤盖住。
在该场景中，鲶鱼 $0$（在单元 $(0, 2)$ 中）和鲶鱼 $3$（在单元 $(3, 3)$ 中）能被抓住。
鲶鱼 $1$（在单元 $(1, 1)$ 中）没被抓住，因为有一个长堤盖住了它所在的单元；鲶鱼 $2$（在单元 $(4, 4)$ 中）没被抓住，因为没有长堤紧邻它的西侧或东侧。
Bu Dengklek 希望造出来的长堤能让被抓住的鲶鱼的总重量尽量大。
你的任务是求出 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。
输入格式
无
输出格式
无
说明/提示
### 约束条件
* $2 \le N \le 100\;000$
* $1 \le M \le 300\;000$
* $0 \le X_i \le N - 1$，$0 \le Y_i \le N - 1$（对所有满足 $0 \le i \le M - 1$ 的 $i$）
* $1 \le W_i \le 10^9$（对所有满足 $0 \le i \le M - 1$ 的 $i$）
* 任意两条鲶鱼都不会在同一单元中。
换句话说，$X_i \neq X[j]$ 或 $Y_i \neq Y[j]$（对于所有满足 $0 \le i \lt j \le M - 1$ 的 $i$ 和 $j$）。
### 子任务
1. （3 分） $X_i$ 是偶数（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （6 分） $X_i \le 1$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （9 分） $Y_i = 0$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （14 分） $N \le 300$，$Y_i \le 8$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （21 分） $N \le 300$
1. （17 分） $N \le 3000$
1. （14 分） 在每列中至多有 $2$ 条鲶鱼。
1. （16 分） 没有额外限制。
### 评测程序示例
评测程序示例读取如下格式的输入：
* 第 $1$ 行：$N \; M$
* 第 $2 + i$ 行（$0 \le i \le M - 1$）：$X_i \; Y_i \; W_i$
评测程序示例将按照如下格式打印你的答案：
* 第 $1$ 行：`max_weights` 的返回值
### 约定
题面在给出函数接口时，会使用一般性的类型名称 `void`、`int`、`int64`、`int[]`（数组）和 `int[][]`（数组的数组）。
在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：
| `void ` | `int` | `int64` | `int[]` |
| ------- | ----- | ----------- | ------------------ |
| `void ` | `int` | `long long` | `std::vector` |
| `int[][]` | 数组 `a` 的长度 |
| ------------------------------- | ------------------- |
| `std::vector` | `a.size()` |