Во владениях короля Флатландии находится прямая дорога длиной \(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\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, …, a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3 = a_2 + a_4, …, a_{n-1} = a_{n-2} + a_n\). Например, последовательность \([1, 2, 1, –1]\) является гармоничной, поскольку \(2 = 1 + 1\), и \(1 = 2 + (–1)\).

Рассмотрим последовательности равной длины: \(A = [a_1, a_2, …, a_n]\) и \(B = [b_1, b_2, …, b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A, B) = |a_1 – b_1| + |a_2 – b_2| + … + |a_n – b_n|\). Например, \(d([1, 2 ,1, –1], [1, 2, 0, 0]) = |1 – 1| + |2 – 2| + |1 – 0| + |–1 – 0| = 0 + 0 + 1 + 1 = 2.\)

В конце лекции профессор написал на доске последовательность из \(n\) целых чисел \(B = [b_1, b_2, …, b_n]\) и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A = [a_1, a_2, …, a_n]\), такую, что \(d\)(\(A\), \(B\)) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A, B)\).

Требуется написать программу, которая по заданной последовательности \(B\) определяет, на каком минимальном расстоянии от последовательности \(B\) найдется гармоничная последовательность \(A\).