G. Ограничения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы планируете строить дома на улице. На улице есть $$$n$$$ мест, где вы можете построить дома. Все они пронумерованы слева направо от $$$1$$$ до $$$n$$$. В каждом из них вы можете построить дом с целочисленной высотой от $$$0$$$ до $$$h$$$.

За каждый дом вы получаете прибыль в размере $$$a^2$$$ долларов, где $$$a$$$ — высота этого дома.

У города есть $$$m$$$ ограничений. $$$i$$$-е ограничение говорит о том, что если самый высокий дом от $$$l_i$$$ до $$$r_i$$$ строго больше, чем $$$x_i$$$, вы должны заплатить штраф в размере $$$c_i$$$ долларов.

Вы хотели бы построить дома, чтобы максимизировать свою чистую прибыль (прибыль минус штрафы). Определите максимально возможную прибыль.

Входные данные

Первая строка содержит три целых числа $$$n,h,m$$$ ($$$1 \leq n,h,m \leq 50$$$) — количество мест для постройки домов, максимальная высота и количество ограничений соответственно.

Каждая из следующих $$$m$$$ строк содержит четыре целых числа $$$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$$$).

Выходные данные

Выведите одно целое число — максимальную прибыль, которую вы можете получить.

Примеры
Входные данные
3 3 3
1 1 1 1000
2 2 3 1000
3 3 2 1000
Выходные данные
14
Входные данные
4 10 2
2 3 8 76
3 4 7 39
Выходные данные
289
Примечание

В первом примере оптимальным является строительство домов высотой $$$[1, 3, 2]$$$. Мы получаем прибыль в размере $$$1^2+3^2+2^2 = 14$$$. Мы не нарушаем никаких ограничений, поэтому никаких штрафов нет, поэтому общая прибыль составляет $$$14 - 0 = 14$$$.

Во втором примере оптимально строить дома высотой $$$[10, 8, 8, 10]$$$. Мы получаем прибыль в размере $$$10^2+8^2+8^2+10^2 = 328$$$, и мы нарушаем второе ограничение и платим штраф в $$$39$$$ долларов, таким образом, общая прибыль составляет $$$328-39 = 289$$$. Обратите внимание, что даже при отсутствии ограничения на дом $$$1$$$, мы все равно не можем иметь высоту выше $$$10$$$ метров.