T266504 「DTOI-1」Hotel

>滑稽怪住进了有着 $10^{100000000000000000}$ 层高的「滑稽公寓」，可是公寓顶端的天花板却会漏水。

**本题数据有误，已重新上传数据。** 公寓有一个大小为 $n\times n$ 的屋顶，由 $n^2$ 块面积相等的瓦片组成，坐标为 $(i,j)$ 的瓦片的高度是 $a_{i,j}$。坐标为 $(n,n)$ 的瓦片高度为 $0$，且水流到此瓦片上时会直接流到地面，因此瓦片 $(n,n)$ 无论接到多少水，瓦片上水的高度恒为 $0$。 现在下起了大雨，但由于降水不均匀，每秒会有一个区域接到 $k_i$ 个单位高的水。你可以（**而非必须**）将一个瓦片上的 $1$ 个单位高的水引流到上下左右某个「水位」（定义一个瓦片的「水位」为 这个瓦片的高度 与 瓦片上水的高度 之和）**严格**低于它的「水位」的另一个瓦片上，**且引流后，被引流位置的水位不得高于引流位置的水位**，假定此操作不消耗时间，且可以执行任意次。 给定 所有瓦片的高度 和 每秒的降水信息，求经过 $m$ 秒后，屋顶水量（屋顶水量为所有瓦片上水的高度之和）的最小值。

第一行，两个整数 $n,m$。 接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数表示 $a_{i,j}$。 接下来 $m$ 行，每行五个整数 $x_{1,i},y_{1,i},x_{2,i},y_{2,i},k_i$，分别表示 降水区域左上角的横纵坐标、降水区域右下角的横纵坐标 和 降水高度，**保证描述区域存在**。

一行一个整数，表示屋顶水量的最小值。

#### 样例解释 第一秒，$(1,2)$ 接到 $2$ 单位高的水，全部流入 $(2,2)$ 。 第二秒，所有瓦片接到 $3$ 单位高的水。先将$(1,2)$ 和 $(2,1)$ 的水全部流入 $(2,2)$，再将 $(1,1)$ 的 $1$ 单位高的水流入 $(2,1)$，最后将 $(2,1)$ 的 $1$ 单位高的水流入 $(2,2)$，此时屋顶只有 $(1,1)$ 有 $2$ 单位高的水。 综上可得答案为 $2$，没有更小的答案。 #### 数据范围 | SubTask | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $0$ | $A,C$ | $10$ | | $1$ | $B,C$ | $20$ | | $2$ | $C$ | $30$ | | $3$ | 无特殊限制 | $40$ | 性质 $A$：所有 $a_{i,j}$ 都相等（$i$，$j$ 不能同时为 $n$）。 性质 $B$：$1 \le n \le 50$。 性质 $C$：$x_{1,i}=x_{2,i}$，$y_{1,i}=y_{2,i}$。 对于 $100\%$ 的数据，有 $1 \le n \le 500$，$1 \le k_i,a_{i,j} \le 10^4(i\neq n\ \operatorname{or}\ j\neq n,a_{n,n}=0)$，$1 \le m \le 2 \times 10^5$。