题目背景

译自 PA 2019 Final。$\texttt{3s,512M}$。

本题数据为自造。

std：zimpha，validator：Starrykiller，generator：KanameMadoka。

题目描述

一个长为 $X$ 宽为 $Y$ 的矩形被分为 $X\times Y$ 个方格。我们记第 $i$ 行第 $j$ 列的方格为 $(i,j)$。

有 $n$ 种动物。第 $i$ 种动物不喜欢待在以 $(x_i,y_i)$ 和 $(x_i',y_i')$ 为对角顶点确定的矩形内。我们保证这个矩形严格包含于 $X\times Y$ 的矩形。

第 $i$ 种动物有 $c_i$ 只。那么，一共有 $S=c_1+c_2+\cdots+c_n$ 只动物。

现在要将每只动物放在一个方格里面。一个方格里面可以放多只动物，但是一只动物不能待在它不喜欢的区域。

记 $(i,j)$ 内有 $p_{i,j}$ 只动物，那么这种分配方式的得分为 $\displaystyle \sum_{1\le i\le X}\sum_{1\le j\le Y} {p_{i,j}\choose 2}$。这里，$\displaystyle {a\choose 2}=\frac{a(a-1)}{2}$。

找到合法的分配方式中得分最大的那个分配方式。只需要输出最大的得分。

输入格式

第一行，三个正整数 $n,X,Y$。

接下来 $n$ 行，每行五个正整数 $x_i,y_i,x'_i,y'_i,c_i$。

输出格式

输出一行一个正整数，表示答案。

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

9

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

3

提示

• $1\le n\le 10^5$；
• $1\le X,Y\le 10^3$；
• $\textcolor{red}{1\le x_i\le x'_i\le X},\textcolor{red}{1\le y_i\le y'_i\le Y}$；
• 以下条件中，至少有一个成立：${x_i\neq 1},{y_i\neq 1},{x'_i\neq X},{y'_i\neq Y}$；
• $1\le c_i\le 10^3$。

样例解释：

对于第一个样例，只能把第一种动物全部放在 $(1,2)$，第二种动物全部放在 $(1,1)$，得分为 $\binom{4}{2}+\binom{3}{2}=9$。

对于第二个样例，最优方案为把三种动物都全部放在 $(4,1)$，得分为 $\binom{3}{2}=3$。容易证明没有比其更优的答案。