题目描述

农夫约翰计划把他的 $N$ 头奶牛带到集市上去展览，他想尽可能多地带去不同种类的奶牛。一头奶牛的特征用其身上的斑点数量来表示。

一块平地（坐标范围 $1 \le r, c \le 2\,000\,000$）被分成 $1 \times 1$ 的方块，每头牛都放在某一个方块中。每头牛身上有 $S$ 个斑点。

给定两个整数 $A$ 和 $B$，约翰可以选择一个 $A$ 行 $B$ 列的矩形区域（矩形的边必须与坐标轴平行），并把该区域内的所有牛带去展览。对于任意选定的矩形，它的“差异”定义为该矩形范围内所有牛的斑点数量的最大值与最小值的差的绝对值。如果矩形内没有牛，则无法作为有效选择。

请你计算在所有可能的 $A \times B$ 矩形中，最大的差异值是多少。

输入格式

第一行包含三个整数 $N, A, B$。

接下来 $N$ 行，每行包含三个整数 $r, c, S$，分别表示一头牛所在的行、列以及它身上的斑点数量。

输出格式

输出一个整数，表示最大的差异值。

样例

8 4 2
1 4 9
1 5 8
2 10 2
3 2 6
4 6 1
5 15 3
6 4 5
7 9 4

7

数据范围与提示

• $1 \le N \le 1000$
• $1 \le A, B \le 2\,000\,000$
• $1 \le r, c \le 2\,000\,000$
• $1 \le S \le 2\,000\,000$
• 注意：矩形区域内可能没有牛，此时不能作为有效选择。保证至少存在一个包含牛的矩形。