OpenKattis
POwarmup23 svår: intro DP

Start

2022-11-10 16:00 CET

POwarmup23 svår: intro DP

End

2022-11-17 16:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -504 days 1:11:28

Time elapsed

168:00:00

Time remaining

0:00:00

Problem F
Springoalla

Springoalla älskar att löpträna. Totalt känner hon till $n$ löpspår och hon vet exakt hur lång tid det tar för henne att springa det spåret och sedan tillbaka. Den första gången hon springer på ett nytt spår, så lär hon känna spåret lite bättre. Närmare bestämt lär hon sig var i spåret hon kommit halvvägs, och har då möjlighet att springa tillbaka efter halva spåret. Då blir löptiden halverad. T.ex. kan hon springa ett halvt $20$-minutersspår på $10$ minuter, men bara efter att hon redan sprungit hela spåret en gång.

Springoalla vill löpträna i minst $t$ minuter men hon är också noggrann med att inte träna för länge. Givet tiderna för varje spår, beräkna hur lång tid $t_ s$ hon minst måste springa. Talet $t_ s$ ska alltså vara så litet som möjligt men uppfylla $t_ s\geq t$. Om det finns flera sätt att springa $t_ s$ minuter vill Springoalla springa så litet antal sträckor $n_ s$ som möjligt, där man räknar varje gång hon springer bort från utgångspunkten som en sträcka, oavsett om det är ett helt eller halvt spår. Finns det flera lösningar med samma $t_ s$ och $n_ s$ kan du ange vilken som helst av dem.

Indata

På första raden står två heltal $n$ och $t$, där $1 \leq n \leq 1000$ är antalet löpbanor och $1 \leq t \leq 100\, 000$ är tiden som Springoalla vill löpträna. På andra raden står $n$ stycken heltal $l_ i$, där $1 \leq l_ i \leq 40\, 000$ kommer vara ett jämnt heltal och är antalet minuter det tar att springa löpspår $i$. Talet $t$ behöver däremot inte vara jämnt.

Utdata

Första utdataraden ska innehålla de två heltalen $t_ s$ och $n_ s$: den tid Springoalla måste springa respektive hur många sträckor hon totalt springer. Därefter ska en rad skrivas med $n$ heltal, där det $i$:te heltalet anger hur många minuter Springoalla sprang på spår $i$.

Sample Input 1 Sample Output 1
3 23
10 8 14
23 3
15 8 0 
Sample Input 2 Sample Output 2
3 23
8 12 14
24 2
0 24 0 
Sample Input 3 Sample Output 3
1 3
2
3 2
3 
Sample Input 4 Sample Output 4
1 7
4
8 2
8