Water Tank

Time limit2sMemory limit512 MB

Summary

Given a grid of tank cells with holes in their walls, compute the total water volume left after water drains out through the holes.

Level: Medium5 of 10
Topics: Graph, Shortest path, Heap
Solved: No attempts yet

Problem

A water tank has length $N$ , width $M$ , and height $H$ . $N$ , $M$ , and $H$ are all positive integers. Figure 1 shows a tank with length 2, width 3, and height 5. As Figure 1 shows, the inside of the tank has walls running horizontally and vertically. Each inner cell is a rectangular column with length 1, width 1, and height $H$ . Viewed from above, the tank is a grid of square cells, as in Figure 2. Each cell has four walls, and each wall can have at most one hole. Corners have no holes.

Figure 1

In Figure 1, the height of each hole is measured from the floor. The top view in Figure 2 shows which wall and which height each hole is on. It also marks hole positions that Figure 1 cannot show. As Figure 2 shows, interior walls can have holes too.

Figure 2

To fill the tank, first plug every hole so no water leaks out. Then fill the whole tank through the water supply device above each cell. After the tank is full, remove all the plugs. Water flows out through the holes into adjacent rooms or outside. After some time, the water stops flowing. At that point, the water level in each cell can differ.

For reference, the water heights left in each cell of Figure 2 are the numbers in parentheses in Figure 3.

Figure 3

Ignoring wall thickness, write a program that computes the total volume of water left in the tank.

Input

The first line contains three positive integers $N$ , $M$ , and $H$ , the length, width, and height of the tank.

The next line contains $M$ integers, the hole heights in the first horizontal wall, from left to right. Each value is an integer from 0 to $H-1$ . A value of -1 means that wall has no hole. The next line gives the second horizontal wall, and so on, so that $N+1$ lines cover all horizontal walls.

The next line contains $M+1$ integers, the hole heights in the vertical walls of the cells that share the first horizontal wall, starting from the first vertical wall. The next line gives the vertical walls of the next row of cells. In total, $N$ lines give all the vertical wall holes.

Output

Print the total volume of water left in the tank once water no longer flows out.

Examples2

Example 1

Input

2 3 5
1 -1 -1
3 2 -1
4 -1 2
-1 -1 4 3
-1 -1 -1 -1

Expected output

Example 2

Input

1 5 10
5 -1 -1 -1 6
-1 7 -1 6 -1
-1 2 8 4 2 3

Expected output