Вы планируете строить дома на улице. На улице есть \(n\) мест, где вы можете построить дома. Все они пронумерованы слева направо от \(1\) до \(n\). В каждом из них вы можете построить дом с целочисленной высотой от \(0\) до \(h\).
За каждый дом вы получаете прибыль в размере \(a^2\) долларов, где \(a\) — высота этого дома.
У города есть \(m\) ограничений. \(i\)-е ограничение говорит о том, что если самый высокий дом от \(l_i\) до \(r_i\) строго больше, чем \(x_i\), вы должны заплатить штраф в размере \(c_i\) долларов.
Вы хотели бы построить дома, чтобы максимизировать свою чистую прибыль (прибыль минус штрафы). Определите максимально возможную прибыль.
Выходные данные
Выведите одно целое число — максимальную прибыль, которую вы можете получить.
Примечание
В первом примере оптимальным является строительство домов высотой \([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\) метров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 3
1 1 1 1000
2 2 3 1000
3 3 2 1000
|
14
|
|
2
|
4 10 2
2 3 8 76
3 4 7 39
|
289
|