Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Zoning Restrictions

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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$$$).

Output

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

Examples

Input

3 3 3 1 1 1 1000 2 2 3 1000 3 3 2 1000

Output

14

Input

4 10 2 2 3 8 76 3 4 7 39

Output

289

Note

In the first example, it's optimal to build houses with heights $$$[1, 3, 2]$$$. We get a gain of $$$1^2+3^2+2^2 = 14$$$. We don't violate any restrictions, so there are no fees, so the total profit is $$$14 - 0 = 14$$$.

In the second example, it's optimal to build houses with heights $$$[10, 8, 8, 10]$$$. We get a gain of $$$10^2+8^2+8^2+10^2 = 328$$$, and we violate the second restriction for a fee of $$$39$$$, thus the total profit is $$$328-39 = 289$$$. Note that even though there isn't a restriction on building $$$1$$$, we must still limit its height to be at most $$$10$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/29/2020 11:55:36 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|