ŠIOM — Užduotys

Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Duomenų failas: uzduotys.in

Rezultatų failas: uzduotys.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Užduotys

Darius turi sąrašą darbų kuriuos jam reikia atlikti. Neseniai jis sužinojo apie naudingą laiko planavimo būdą - jei užduotis užtruks mažiau nei $d$ minučių, tai ją geriausią atlikti iš karto.

Dariaus saraše yra $n$ užduočių. Kiekviena iš jų turi trukmę $p_i$ - tiek minučių užtrunka atlikti užduotį $i$ . Darius per savo sąrašą eina iš eilės, ir jei užduotis užima nedaugiau nei $d$ minučių, tai ją padaro. Jei užduotis trunka daugiau nei $d$ minučių, jis jos nedaro visai.

Kad nepervargtų, Darius kas $m$ užduočių padaro pertrauką. Pertraukos trukmė yra lygi paskutinių $m$ užduočių trukmių sumai.

Pavyzdžiui, jei $n=5,p=[2,4,3,6,1],d=3$ ir $m=2$ , tai Darius užduotis atlikinės taip:

Pirma užduotis trunka 2 minutes, todėl Darius ją padaro.
Antra užduotis trunka 4 minutes, todėl Darius ją praleidžia.
Trečia užduotis trunka 3 minutes, Darius ją padaro.
Darius padarė dvi užduotis, jos užtruko $2+3=5$ minutes, todėl Darius padaro 5 minučių pertrauką.
Ketvirta užduotis per ilga, Darius ją praleidžia.
Penkta užduotis trunka 1 minutę, Darius ją padaro.

Darius ketina nustoti dirbti po lygiai $t$ minučių. Jei tuo metu jis yra pradėjęs daryti kažkokią užduotį bet dar nepabaigė, tai ta užduotis laikoma neatlikta.

Raskite su kokia $d$ reikšme Darius pabaigtų daugiausiai užduočių per $t$ minučių.

Pradiniai duomenys

Pirmoje eilutėje yra skaičiai $n,m$ , ir $t$ ( $1\\leqn\\leq10^5,1\\leqm\\leq2\\times10^5,1\\leqt\\leq4\\times10^{10}$ ) - užduočių skaičius, kas kiek užduočių Darius padaro pertrauką, ir kiek laiko jis ketina dirbti.

Antroje eilutėje yra $n$ skaičių $p_i$ ( $1\\leqp_i\\leq2\\times10^5$ ) - užduočių trukmės.

Rezultatai

Išveskite du skaičius - kiek daugiausiai užduočių Darius gali spėti pabaigti per $t$ minučių, ir kokia tam turi būti reikšmė $d$ . Jei yra kelios galimos $d$ reikšmės, išveskite mažiausią neneigiamą galimą reikšmę.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
5 2 6 2 4 3 6 1	2 2

Šeštadieninė informatikos olimpiadininkų mokykla

Užduotys

Pradiniai duomenys

Rezultatai

Pavyzdžiai