Maximizing Animal Group Score

You are given a grid with X rows and Y columns (a total of X×Y cells). The cell in row i and column j is denoted by (i,j). There are n species of animals. For the i-th species, there are c_i animals, and these animals do not like to be placed in the forbidden region defined by the rectangle with opposite corners at (x_i, y_i) and (x'_i, y'_i). It is guaranteed that for every species the forbidden rectangle is strictly contained in the overall grid. (That is, its boundaries do not touch the grid boundaries.)

You must assign each animal to one of the grid cells. Multiple animals (even of different species) can be placed in the same cell, but an animal cannot be placed in a cell that lies inside its species’ forbidden region.

Suppose cell (i,j) contains p_i,j animals. The score of an assignment is defined as \[ \text{score} = \sum_{1 \le i \le X}\sum_{1 \le j \le Y} {p_{i,j} \choose 2} = \sum_{i,j} \frac{p_{i,j}(p_{i,j}-1)}{2}. \]

Your task is to find the maximum possible score among all valid assignments. Note that since the forbidden rectangles are strictly contained in the grid, each species is allowed to be placed in any of the four corner cells of the grid. Hence, an optimal strategy is to put all animals in one of these common cells, yielding the maximum score of \[ \frac{S(S-1)}{2},\quad \text{where } S = c_1+c_2+\cdots+c_n. \]

Output the maximum score.

inputFormat

The input is given as follows:

The first line contains three integers X, Y and n -- the number of rows, the number of columns, and the number of species respectively.

Then, n lines follow. The i-th of these lines contains five integers: x_i y_i x'_i y'_i c_i, where (x_i, y_i) and (x'_i, y'_i) are the opposite corners of the forbidden rectangle for the i-th species, and c_i is the number of animals of that species.

It is guaranteed that the forbidden rectangle for each species is strictly contained within the grid.

outputFormat

Output a single integer, the maximum possible score, which is equal to (\dfrac{S(S-1)}{2}), where (S = c_1+ c_2+ \cdots+ c_n).

sample

5 5 2
2 2 3 3 2
2 2 3 3 3

10