← 返回题目列表

Codeforces · 1221/F

F. 选择一个正方形

中文机器翻译题面 查看原题

Petya最近发现了一款​​游戏“选择方块”。在这个游戏中,在无限的场地上有$$$n$$$个点,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i)$$$,成本为 $$$c_i$$$。

你必须选择一个正方形,其边与坐标轴平行,左下角和右上角属于线$$$y = x$$$,并且所有角都有整数坐标。

您获得的分数是所选正方形覆盖的点的成本总和减去正方形边长。请注意,边的长度可以为零。

Petya 要求您计算游戏中通过恰好放置一个方块可以获得的最大可能得分。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 字段上的点数。

以下 $$$n$$$ 行包含三个整数 $$$x_i, y_i, c_i$$$ ($$$0 \le x_i, y_i \le 10^9, -10^6 \le c_i \le 10^6$$$) — 分别是第 $$$i$$$ 个点的坐标及其成本。

输出

在第一行中打印 Petya 可以达到的最大分数。

在第二行中打印四个整数 $$$x_1, y_1, x_2, y_2$$$ ($$$0 \le x_1, y_1, x_2, y_2 \le 2 \cdot 10^9, x_1 = y_1, x_2 = y_2, x_1 \le x_2$$$),用空格分隔 — 坐标Petya 必须选择方格的左下角和右上角才能获得最高分。

示例

输入 #1

6
0 0 2
1 0 -5
1 1 3
2 3 4
1 4 -4
3 1 -1

输出 #1

4
1 1 3 3

输入 #2

5
3 3 0
3 3 -3
0 2 -1
3 1 3
0 0 -2

输出 #2

0
1 1 1 1

注意

第一个示例对应的字段: