Во владениях короля Флатландии находится прямая дорога длиной \(n\) километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

У короля три сына: младший, средний и старший. Король решил, что в заповедник не войдут участки лесного массива, которые он оставит сыновьям в наследство. При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:

• каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры \(a \times a, b \times b\) и \(c \times c\);
• стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна \(n\);
• участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство \(a < b < c\);
• суммарная площадь участков \(a^2 + b^2+ c^2\) должна быть минимальна.

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

В НИИ метеорологии решили изучить процесс образования водоемов на различных рельефах местности во время дождя. Ввиду сложности реальной задачи была создана двумерная модель, в которой местность имеет только два измерения — высоту и длину. В этой модели рельеф местности можно представить как N-звенную ломаную c вершинами \((x_0, y_0), ..., (x_N, y_N)\), где \(x_0 < x_1 < ... < x_N\) и \(y_i \neq y_j\), для любых \(i \neq j\). Слева в точке \(x_0\) и справа в точке \(x_N\) рельеф ограничен вертикальными горами огромной высоты.

Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины H. Но поскольку рельеф — это ломаная, то вода стекает и скапливается в углублениях, образуя водоемы.

Требуется найти максимальную глубину в образовавшихся после дождя водоемах.

Прямоугольная детская площадка полностью замощена \(N\) плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.

На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь.

Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.