Вы планируете строить дома на улице. На улице есть \(n\) мест, где вы можете построить дома. Эти места пронумерованы слева направо от \(1\) до \(n\). В каждом месте вы можете построить дом с целочисленной высотой от \(0\) до \(h\).
В каждом месте, если дом имеет высоту \(a\), вы получите от него прибыль в размере \(a^2\) долларов.
Город имеет \(m\) ограничений. В соответствии с \(i\)-м ограничением, самый высокий дом от \(l_i\) до \(r_i\) (включительно) должен иметь высоту не более \(x_i\).
Вы хотели бы построить дома, чтобы максимизировать свою прибыль. Определите максимально возможную прибыль.
Примечание
В первом примере можно построить \(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\)).