3D Tetris Height Calculation

In a 3-dimensional version of Tetris, cuboids fall down on a rectangular platform. Each block falls vertically until it hits the platform or an existing block, and then it comes to rest in that exact position. The twist in this puzzle is that the blocks fall one by one in a given order, and the player’s task is to determine the height of the highest point after all blocks have fallen.

Each block is described by its starting coordinate (x, y), the dimensions of its base (width w and depth d), and its height h. When a block falls, it lands on the highest point underneath its entire base. Mathematically, if the block covers the region \([x,x+w-1]\times[y,y+d-1]\), then its landing height is computed as:

$$ H_{land} = \max_{(i,j) \in [x,x+w-1]\times[y,y+d-1]} H(i,j) + h, $$

where \(H(i,j)\) is the current height at point \((i,j)\) before the block falls. Once the block lands, all points in its base region are updated to this new height \(H_{land}\). Your task is to compute the maximum height among all points on the platform after all blocks have fallen.

inputFormat

The first line of input contains a single integer \(n\) indicating the number of blocks. Each of the next \(n\) lines contains five integers: \(x\), \(y\), \(w\), \(d\), and \(h\). Here, \((x, y)\) represents the bottom-left coordinates of the block, \(w\) and \(d\) represent the width and depth of its base respectively, and \(h\) is the height of the block.

outputFormat

Output a single integer, which is the maximum height reached on the platform after all blocks have fallen and settled.

sample

1
0 0 2 2 5

5