Cena rekurze

Rekurzivní algoritmus A, který má na vstupu pole délky N, probíhá takto:
Aktuálně zpracovávaný úsek pole se rozdělí na k částí. Tyto části se rekurzivně zpracují stejným algoritmem A a poté se z výsledků práce nad jednotlivými úseky sestaví výsledek. Pokud je délka aktuálního úseku rovna 1, rekurze končí a algoritmus dál sám sebe nevolá. Pokud je délka d aktuálního úseku větší než 1 a menší nebo rovna k, předá se do rekurzivního zpracování právě d úseků obsahujících pravě jeden prvek. Algoritmus se vždy snaží dělit aktuální úsek na menší úseky identické délky. Když to nejde, to jest, když délka aktuálního úseku není násobkem k, pak velikost každých dvou menších úseků, které se předávají rekurzivnímu zpracování, se navzájem liší maximálně o 1 prvek.

Cena zpracování jednoprvkového úseku je zanedbatelná, zato cena zpracování každého úseku délky M, 1 < M ≤ N je dána kvadratickou funkcí
aM2+bM+c.
Tato cena se platí za rozdělění úseku na menší části a pozdější spojení výsledků práce algoritmu nad těmito částmi. Cena algoritmu A nad polem délky N je pak rovna součtu všech cen za dělení a slučování výsledků nad některým úsekem pole. Za úsek považujeme i celé pole délky N.

Parametr k není dán pevně, můžeme jej vybírat z určitého intervalu, a proto vzniká otázka, při které hodnotě k bude celková cena za zpracování celého pole délky N minimální. Když budeme vědět, pro kterou hodnotu k minimum nastává a jakou má hodnotu, ještě zjistíme, kolikrát se musela provést akce dělení nějakého úseku na menší úseky.

Vstup

Na vstupu je textový soubor obsahující jediný řádek. Na řádku jsou uvedena celá čísla N, a, b, c, k1, k2 v tomto pořadí oddělená navzájem jednou mezerou. Pro zadané parametry platí:
2 < N < 260,
0 ≤ a < 1000,
−1000 ≤ b, c < 1000,
2 ≤ k1 ≤ k2 ≤ 10000.
Data jsou zadána korektně, není nutno je kontrolovat.

Výstup

Na výstupu je jediný řádek se třemi celými čísly navzájem oddělenými mezerou. První číslo představuje hodnotu k, při níž je cena algoritmu A nad polem dané délky N nejnižší, druhé číslo představuje tuto cenu a třetí udává, kolikrát celkově při běhu A nad daným polem a při této hodnotě k došlo k dělení nějakého úseku. Výsledná cena je v rozmezí −260 ... 260.

Příklad

Vstup:
7 0 -1 2 2 3
Výstup:
2 -8 6

Příklad 2

Vstup:
5 1 0 3 2 4
Výstup:
4 35 2

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data