Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Након расправе са часа филозофије, малом Стојану је пала на памет нова пословна идеја – одлучио је да се бави куповином и продајом струје. На основу изгубљеног Теслиног изума је направио батерију бесконачног капацитета, тако да сада може да купује струју данима када је јефтина и продаје је када је скупа.
Помоћу временске машине (такође Теслиног изума), Стојан је сазнао колика ће бити цена струје сваког од наредних \(N\) дана (\(i\)-тог дана ће киловат-час коштати \(C_i\) динара). На почетку му је на располагању \(M\) динара и празна батерија. Сваког дана он може да купи колико год жели струје (док год има новца да је плати) или прода колико год жели (док год има довољно струје у батерији). Количине купљене и продате струје не морају бити цели бројеви.
Помозите Стојану да одлучи како ће трговати струјом, тако да му на крају последњег дана остане што више новца.
У првој линији стандардног улаза налазе се два цела броја, \(N\) и \(M\) – број дана за које Стојан зна цену струје и свота новца која му је на располагању на почетку.
У другој (последњој) линији налази се \(N\) бројева \(C_1, C_2, \ldots, C_N\), где је \(C_i\) цена једног киловат-часа \(i\)-тог дана.
На прву линију стандардног излаза исписати максималну суму новца коју Стојан може имати на крају последњег дана. Гарантује се да ова вредност неће бити већа од \(10^{10}\).
4 10
4 10 5 201003 21
10 8 321У првом примеру, Стојан може да купи \(2.5\) киловат-часова првог дана, и прода их другог дана за \(25\) динара. Трећег дана може да купи пет киловат-часова и прода их четвртог за \(100\) динара, што је и оптимално решење.
У другом примеру, најбоље је да уопште не купује струју и сачува \(21\) динар са којим је почео.
Aко је ваш програм исписао број \(a\), а решење комисије је реалан број \(b\), ваше решење се прихвата као тачно под условом да важи \(\frac{|a-b|}{b} \leq 10^{-6}\) или важи \(|a-b| \leq 10^{-6}\).