P12463 [Ynoi Easy Round 2018] 星野瑠美衣


星野露比喜欢在二维平面上巡游。她永远在整点上，并且每一步只可能从上下左右中选一个（即，将横坐标或纵坐标 $+1$ 或 $-1$）。 对于二维平面上 $N$ $(N \ge 1)$ 个整点 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$，我们称它们描述的一次**巡游**是星野露比从 $(X_1, Y_1)$ 出发，按顺序依次经过 $(X_2, Y_2), (X_3, Y_3), \dots, (X_N, Y_N)$ 并回到 $(X_1, Y_1)$ 的一个过程。我们将一次巡游中星野露比所需要的**最小步数**称为这次巡游的**兴奋值**。 星野露比现在想要进行一次巡游。她首先选定了二维平面上 $n$ 个整点 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，并准备在它们之间再插入一些点，来确定他下一次巡游所需要经过的点。 于是她又找到了二维平面上 $m$ 个整点 $(x'_1, y'_1), (x'_2, y'_2), \dots, (x'_m, y'_m)$。对于其中每个整点 $(x'_j, y'_j)$，其具有一个**收益** $w_j$（可能为负）；他可以选择一个先前的 $n$ 个整点中的某一者 $(x_i, y_i)$，并将 $(x'_j, y'_j)$ **插入**到 $(x_i, y_i)$ **之后**。当然，她也可以选择不插入到任何位置。 但为了不让巡游变得太复杂，她规定每个 $(x_i, y_i)$ 之后只能插入至多一个整点。 现在，对于 $k=1,2,\dots,n$，他想知道**恰好**插入 $k$ 个点之后，下次巡游的兴奋值与选择插入的整点的总收益之和最大能达到多少。

无

无

Idea：Aleph1022，Solution：Aleph1022&zx2003，Code：Aleph1022，Data：Aleph1022 ### 样例解释 #1 选择 $1$ 个点的一种最优解会将巡游变为 $(1, 1), (7, 9), (2, 2), (4, 3)$，兴奋值为 $34$，并具有 $1$ 的收益，共 $35$。 选择 $2$ 个点的一种最优解会将巡游变为 $(1, 1), (7, 9), (2, 2), (4, 3), (6, 6)$，兴奋值为 $44$，并具有 $3$ 的收益，共 $47$。 选择 $3$ 个点的一种最优解会将巡游变为 $(1, 1), (7, 9), (2, 2), (5, 4), (4, 3), (6, 6)$，兴奋值为 $48$，并具有 $0$ 的收益，共 $48$。 ### 样例解释 #2 选择 $1$ 个点的一种最优方案为 $(0, 4), (5, 1), (3, 4), (0, 1)$。 选择 $2$ 个点的一种最优方案为 $(0, 4), (5, 1), (0, 1), (3, 4), (3, 1)$。 选择 $3$ 个点的一种最优方案为 $(0, 4), (4, 3), (5, 1), (0, 1), (3, 4), (3, 1)$。 ## 数据范围 对于 $15\%$ 的数据，$m \le 10$。 对于 $30\%$ 的数据，$m \le 200$。 对于 $40\%$ 的数据，$m \le 600$。 对于 $60\%$ 的数据，$m \le 10^3$。 对于 $100\%$ 的数据，$1 \le n \le m \le 10^5$，$|x_i|,|y_i|,|x'_j|,|y'_j|,|w_j| \le 10^8$。