Al bell mig del pati de l'Institut Sabadell, des de fa més de mig segle, hi ha un pou que ha estat testimoni silenciós de la història del nostre centre. Construït el 1960, durant les obres de l'edifici principal, aquest pou no era només un element decoratiu - era la font principal d'aigua per a tot l'institut en aquells primers anys, quan el barri tot just començava a créixer i les infraestructures encara eren precàries.

Els alumnes i professors més veterans recorden com, durant els primers anys, les galledes pujaven i baixaven constantment, proporcionant aigua fresca per a la cuina, els lavabos i, fins i tot, per regar el petit hort que hi havia al costat del gimnàs. Va ser precisament un grup d'estudiants dels anys 70 qui, van començar a anomenar-lo "El Pozo". El nom va arrelar ràpidament, i aviat tothom el coneixia així, convertint-se en un punt de trobada habitual: "Ens veiem a El Pozo a l'hora del pati!"

El Pozo no només era una eina productiva per l'Institut. També duia una certa frescor a l'Institut. Amb la seva politja i treball constant, el Pozo sempre duia aigua. No només això, sinó que va contribuïr a apagar més d'un incendi que s'havia provocat a l'Institut.

Amb el pas dels anys, quan l'aigua corrent ja arribava a tot arreu, El Pozo va mantenir el seu paper central en la vida de l'institut, ara com a símbol i testimoni de la nostra història. Generacions d'estudiants han deixat les seves inicials gravades discretament en el seu brocal de pedra, han compartit secrets recolzats en les seves parets, i han fet fotografies de promoció al seu voltant.

Ara, després de 60 anys fidels, arriba el moment de jubilar El Pozo. En aquesta CodeJam, volem retre homenatge al pou. El vostre repte? Ajudar-nos a llançar una última galleda a El Pozo!

El pas del temps no perdona, i després d'anys en desús, les parets interiors d'El Pozo s'han omplert de teranyines. El pou té una profunditat de $N$ unitats i una amplada de $H$ unitats i les teranyines s'han format alternativament des de les parets laterals. La primera teranyina surt de la paret esquerra, i després s'alternen entre dreta i esquerra al llarg de tota la profunditat del pou.

Volem llançar una última galleda commemorativa al fons d'El Pozo. La galleda, en comptes d'esquivar les teranyines, baixarà en línia recta en una posició horitzontal fixa, trencant totes les teranyines que trobi en el seu camí.

Per exemple, si tenim aquest dibuix de El Pozo (la imatge correspón al segon exemple)

i llancessim la galleda desde la 4a posició, trencaria 8 teranyines

Aquesta no és la solució òptima ja que si l'haguessim llençat desde la primera o cinquena posició, només trencariem 7 teranyines

Fes un programa per determinar quina és el mínim nombre de teranyines que trencaria aquesta última galleda conmemorativa, i desde quantes posicions es podria llançar.

Entrada

La primera línia conté dos enters $N$ i $H (2≤N≤200000, 2≤H≤500000)$, on N és la profunditat del pou, i el nombre de teranyines i H és l'amplada del pou. N sempre serà parell. Les següents N línies contenen la longitud de cada teranyina, una per línia. Totes les longituds són enters positius menors que H.

Sortida

Una línia amb dos enters separats per un espai:

El nombre mínim de teranyines que la galleda haurà de trencar El nombre de posicions horitzontals diferents on es pot aconseguir aquest mínim

Exemple d'Entrada

6 7
1
5
3
3
5
1

Exemple de Sortirda

2 3

Exemple d'Entrada

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

Exemple de Sortirda

7 2

Nota

Aquest problema està dedicat a la professora Elena del Pozo, qui ha dedicat la seva carrera a l'ensenyament i ha organitzat nombroses CodeJams que han inspirat a molts estudiants a descobrir la màgia de la programació. La seva dedicació i passió per l'ensenyament han deixat una empremta inesborrable en l'Institut Sabadell, igual que El Pozo ha estat una part fonamental de la història d'aquest centre fictici.