Problem C
Konsultarbeten

I den datorgenererade världen Matriks jobbar du som konsult åt olika hippa IT-företag som behöver unika rutschkanor till sina coola kontor. Under det föregående året fick du ett antal jobberbjudanden vid olika tidpunkter, mätt i millisekunder sedan årets början. För varje jobb kunde du välja om du skulle designa en liten, medelstor eller gigantisk rutschkana åt företaget, vilket tar $2 \cdot 10^5$, $3 \cdot 10^5$ respektive $4 \cdot 10^5$ millisekunder, vilket påbörjas omedelbart efter att erbjudandet gavs (om du tackade ja till det). Under tiden du utför ett uppdrag måste du tacka nej till alla andra erbjudanden som dyker upp under den tiden. När du tittar tillbaka på året är du på intet sätt missnöjd (vem kan klaga på att jobba med rutschkanedesign?), men kanske hade du kunnat välja vilka jobb du tog på ett sätt som hade gett dig en större inkomst. Du fakturerar din kunder $1$ kaka per $10^5$ millisekunder som du jobbar. Om du hade valt uppdragen och deras längder på ett optimalt sätt, hur många kakor hade du kunnat tjäna?

Indata

Den första raden innehåller ett heltal $N$ ($1 \le N \le 10^5$), antalet jobberbjudanden du fick under året.

Den andra och sista raden innehåller $N$ heltal separerade med blanksteg, tiderna då du fick ett jobberbjudande mätt i millisekunder från årets början. Ett år innehåller $31\, 556\, 926 \cdot 10^3$ millisekunder. Det är garanterat att varje jobberbjudande kom minst $4 \cdot 10^5$ millisekunder innan årets slut.

Utdata

Skriv ut ett heltal, antalet kakor du hade kunnat tjäna som mest under året.

Förklaring av exempel 1

En möjlig lösning är att ta det första, tredje och fjärde uppdraget och bygga en gigantisk rutschkana för varje och fakturera $12$ kakor. Dessa tre uppdrag har minst $4 \cdot 10^5$ millisekunder mellan sina starttider, så inget överlappar med något annat.

4
10000 400000 500000 900000

12

5
8 10 2 1000000 30556926000

12

4
100000 400000 400000 700000

10