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

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

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

Город имеет $$$m$$$ ограничений. В соответствии с $$$i$$$-м ограничением, самый высокий дом от $$$l_i$$$ до $$$r_i$$$ (включительно) должен иметь высоту не более $$$x_i$$$.

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

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

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

Каждая из следующих $$$m$$$ содержит три целых числа $$$l_i$$$, $$$r_i$$$ и $$$x_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$0 \leq x_i \leq h$$$) — левая и правая граница (включительно) $$$i$$$-го ограничения и максимальная возможная высота на этом отрезке.

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

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

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

В первом примере можно построить $$$3$$$ дома, максимальная высота которых — $$$3$$$, а также есть $$$3$$$ ограничения. Первое ограничение говорит, что самый высокий дом между $$$1$$$ и $$$1$$$ должен иметь высоту не более $$$1$$$. Второе ограничение говорит, что самый высокий дом между $$$2$$$ и $$$2$$$ должен иметь высоту не более $$$3$$$. Третье ограничение говорит, что самый высокий дом между $$$3$$$ и $$$3$$$ должен иметь высоту не более $$$2$$$.

В этом случае оптимально строить дома высотой $$$[1, 3, 2]$$$. Это вписывается во все ограничения. Общая прибыль в этом случае составляет $$$1^2 + 3^2 + 2^2 = 14$$$.

Во втором примере можно построить $$$4$$$ дома, максимальная высота которых — $$$10$$$, а также есть $$$2$$$ ограничения. Первое ограничение говорит, что самый высокий дом от $$$2$$$ до $$$3$$$ должен иметь высоту не более $$$8$$$. Второе ограничение говорит, что самый высокий дом от $$$3$$$ до $$$4$$$ должен иметь высоту не более $$$7$$$.

В этом случае оптимально строить дома высотой $$$[10, 8, 7, 7]$$$. Мы получаем прибыль в размере $$$10^2+8^2+7^2+7^2 = 262$$$. Обратите внимание, что есть два ограничения на дом $$$3$$$, и оба они должны выполняться. Кроме того, обратите внимание, что хотя нет никаких явных ограничений на дом $$$1$$$, мы все равно должны ограничить его высоту не более $$$10$$$ ($$$h=10$$$).