A12520 | Zoning Restrictions

You are planning to build housing on a street. There are $n$ spots available on the street on which you can build a house. The spots are labeled from $1$ to $n$ from left to right. In each spot, you can build a house with an integer height between $0$ and $h$ .

In each spot, if a house has height $a$ , you can gain $a^2$ dollars from it.

The city has $m$ zoning restrictions though. The $i$ -th restriction says that if the tallest house from spots $l_i$ to $r_i$ is strictly more than $x_i$ , you must pay a fine of $c_i$ .

You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.

The first line contains three integers $n,h,m$ ( $1 \leq n,h,m \leq 50$ ) — the number of spots, the maximum height, and the number of restrictions, respectively.

Each of the next $m$ lines contains four integers $l_i, r_i, x_i, c_i$ ( $1 \leq l_i \leq r_i \leq n$ , $0 \leq x_i \leq h$ , $1 \leq c_i \leq 5\,000$ ).

Print a single integer denoting the maximum profit you can make.