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

#5496. 「POI2006 R1」3D 俄罗斯方块 Tetris 3D

标签: 传统 | 时间限制: 6000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – I etap Tetris 3D

《俄罗斯方块》的开发者们决定创造一个全新的三维版本，在这个版本中，长方体形状的方块将落在一个矩形平台上。与普通的二维版本类似，方块会按照某个固定的顺序，逐个下落。指定的方块会一直下落，直到遇到平台或其他已经放置好的方块等障碍物时才会停止（并保持其下落时的姿态），并在整个游戏过程中保持在该位置。

然而，新游戏的开发者们决定改变游戏的性质，从一款技巧性游戏转变为一款逻辑游戏。玩家将预先知道方块下落到平面上的顺序及其运动轨迹，并需要给出所有方块下落完成后，形成的结构中最高点的高度。所有方块都是垂直下落，并且在下落过程中不会旋转。为简便起见，我们在平台上建立一个笛卡尔坐标系，其原点位于平台的一个角上，坐标轴与平台的边缘平行。

请你编写一个程序，来自动判断玩家给出的答案是否正确。

请编写一个程序，实现以下功能：

• 从标准输入读取依次下落的方块的描述信息，
• 计算出所有方块下落完成后，方块结构中的最高点，
• 将结果输出到标准输出。

输入格式

输入的第一行包含三个整数 $D, S$ 和 $N$ $(1 \le N \le 20000, 1 \le D, S \le 1000)$，由单个空格隔开，分别表示：平台的长度、平台的宽度以及将要落在平台上的方块数量。

接下来的 $N$ 行是连续方块的描述，每行一个。

每个方块的描述由五个整数组成：$d, s, w, x, y$ $(1 \le d, 0 \le x, d+x \le D, 1 \le s, 0 \le y, s+y \le S, 1 \le w \le 100000)$，分别代表一个长度为 $d$、宽度为 $s$、高度为 $w$ 的方块。该方块将以其尺寸为 $d \times s$ 的面朝下落在平台上，并且方块的长度和宽度将分别与平台的长度和宽度平行。该方块在平台上的投影所占区域的顶点坐标将为：$(x, y), (x+d, y), (x, 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