P0683

[POI2006]Tet-Tetris 3D

[POI2006]Tet-Tetris 3D

Tetris 游戏的作者决定开发一款全新的三维版本。在这个游戏中，许多立方体会落到一块平板上。每个立方体开始下落，直到碰到之前落下的立方体或平板后停止。

现在你将知道每个立方体的尺寸以及落下的位置，请计算所有立方体落下后，最高立方体的高度。所有立方体在下落过程中始终保持竖直，且不会旋转。平板的左下角为坐标原点，平板边界平行于坐标轴。

输入格式

第一行包含三个整数 DD、SS 和 NN，分别表示平板的长度、宽度以及下落立方体的数量，满足 1≤N≤2×1041\le N\le 2\times 10^4，1≤D,S≤1031\le D,S\le 10^3。

接下来 NN 行，每行包含五个整数 dd、ss、ww、xx 和 yy，分别表示立方体的长度、宽度、高度以及落下时左下角的坐标，满足：

  • 1≤d1\le d；
  • 0≤x0\le x；
  • d+x≤Dd+x\le D；
  • 1≤s1\le s；
  • 0≤y0\le y；
  • s+y≤Ss+y\le S；
  • 1≤w≤1051\le w\le 10^5。

立方体的长和宽均平行于平板的坐标轴。立方体落下后，其底面的四个角坐标分别为 (x,y)(x,y)、(x+d,y)(x+d,y)、(x,y+s)(x,y+s) 和 (x+d,y+s)(x+d,y+s)。

输出格式

输出一个整数，表示所有立方体落下后最高的高度。

样例输入

7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2

样例输出

6

数据范围

  • 1≤N≤2×1041\le N\le 2\times 10^4；
  • 1≤D,S≤1031\le D,S\le 10^3；
  • 1≤d1\le d；
  • 0≤x0\le x；
  • d+x≤Dd+x\le D；
  • 1≤s1\le s；
  • 0≤y0\le y；
  • s+y≤Ss+y\le S；
  • 1≤w≤1051\le w\le 10^5。

来源与许可

本题为 POI 2006 试题「Tet-Tetris 3D」，题面与测试数据整理自 BZOJ 1513。

样例 1

输入

7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2

输出

6