[AdditionalFile5521.zip](file://AdditionalFile5521.zip?type=additional_file)

#5521. 「PA 2019 Final」Terytoria 2

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2019 Final Terytoria 2

这一次，Bajtazar 正在研究一个特定自然保护区的动物群。该保护区是一个尺寸为 $X \times Y$ 的矩形，被划分为坐标为 $(x, y)$ 的正方形格子，其中 $1 \leq x \leq X$，$1 \leq y \leq Y$。

我们的勤奋研究员区分了 $n$ 个动物物种，并发现每个物种都不喜欢待在保护区内某个矩形区域（严格小于整个保护区）。对于编号为 $i$ 的物种，这个矩形区域由两个对角顶点 $(x_{i}, y_{i})$ 和 $(x_{i}^{\prime}, y_{i}^{\prime})$ 定义，其中 $x_{i} \leq x_{i}^{\prime}$ 且 $y_{i} \leq y_{i}^{\prime}$。我们还知道第 $i$ 个物种有 $c_{i}$ 只动物，因此总动物数量为 $S = c_{1} + c_{2} + \ldots + c_{n}$。

Bajtazar 有一个社会-自然实验的想法，即将每只动物放置在它们物种不喜欢区域之外的某个格子中。放置的“社交性”定义为位于同一格子中的动物对的数量。因此，如果某个格子包含 $p$ 只动物，则该格子对结果的贡献为 $\frac{p \cdot (p-1)}{2}$。

允许将同一物种的两只动物放置在不同的格子中。找出最大可能的社交性值。

输入格式

输入数据的第一行包含三个整数 $n, X, Y$ $(1 \leq n \leq 100000, 1 \leq X, Y \leq 1000)$，分别表示物种数量和保护区的尺寸。

接下来的 $n$ 行每行包含五个整数 $x_{i}, y_{i}, x_{i}^{\prime}, y_{i}^{\prime}, c_{i}$ $(1 \leq x_{i} \leq x_{i}^{\prime} \leq X, 1 \leq y_{i} \leq y_{i}^{\prime} \leq Y, 1 \leq c_{i} \leq 1000)$，描述第 $i$ 个物种不喜欢的区域及其动物数量。对于每个物种，至少满足以下条件之一：$x_{i} \neq 1, y_{i} \neq 1, x_{i}^{\prime} \neq X, y_{i}^{\prime} \neq Y$。

输出格式

输出应包含一个整数，表示放置所有动物后的最大可能社交性值。

样例 1

输入

2 1 2
1 1 1 1 3
1 2 1 2 4

输出

9

在第一个样例中，将 $4$ 只动物放置在坐标 $(1, 1)$ 的格子中，贡献 $\frac{4 \cdot 3}{2}=6$ 对；将剩余 $3$ 只动物放置在坐标 $(1, 2)$ 的格子中，贡献 $\frac{3 \cdot 2}{2}=3$ 对。

样例 2

输入

3 7 3
1 1 3 3 1
5 1 7 3 1
3 2 5 3 1

输出

3

在第二个样例中，所有 $3$ 只动物可以放置在坐标 $(4, 1)$ 的格子中。