注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

请在提交源代码前添加 #include "fish.h"。

题目描述

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 通过造长堤能抓住的鲶鱼的最大总重量。

实现细节

你需要实现下⾯的函数：

int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)

• $N$：池塘的尺寸。
• $M$：鲶鱼的数量。
• $X$, $Y$：长度为 $M$ 的两个数组，给出鲶鱼的位置。
• $W$：长度为 $M$ 的数组，给出鲶鱼的重量。
• 该函数需要返回一个整数，表示 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。
• 该函数将被恰好调用一次。

例子

考虑如下调用：

max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])

该例子的解释请见前面的题面。

在造完所述的长堤后，Bu Dengklek 能抓住鲶鱼 $0$ 和 $3$，其总重量为 $5 + 3 = 8$ 克。 因为无法造出能够抓住总重量超过 $8$ 克的鲶鱼的长堤，函数应当返回 $8$。

约束条件

• $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$）
2. （6 分） $X_i \le 1$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
3. （9 分） $Y_i = 0$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
4. （14 分） $N \le 300$，$Y_i \le 8$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
5. （21 分） $N \le 300$
6. （17 分） $N \le 3000$
7. （14 分） 在每列中至多有 $2$ 条鲶鱼。
8. （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>

int[][]	数组 a 的长度
std::vector<std::vector<int>>	a.size()