Даны четыре действительных числа: A, B, C, D. Найдите все корни уравнения Ax³+Bx²+Cx+D=0. Известно, что все корни этого уравнения не превосходят по абсолютной величине 1000. Известно, что любые два корня этого уравнения различаются не менее, чем на 10^-6.

Вася очень торопится домой, поэтому поднимаясь по лестнице из N ступенек он каждый раз перепрыгивает через одну или две ступеньки (то есть сначала он прыгает на 2-ю или на 3-ю ступеньку, со 2-й он может прыгнуть на 4-ю или на 5-ю и т.д.) Требуется определить количество способов, которыми он может попасть на последнюю, N-ю ступеньку.

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

Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет A_i кубиков.

Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.

Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.

Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.