Problem E
Tavelutrymme

Hosuja ska hålla i en lösningsgenomgång av ett ovanligt klurigt problem. Till sin hjälp har han en whiteboardtavla, samt en röd och en blå penna. Lösningen som han presenterar innehåller $N$ stycken idéer som ska presenteras i ordning, och presentationen av varje idé kräver en viss mängd taveluttrymme.

Hosuja vill använda tiden effektivt, och det kan man inte göra ifall man hela tiden håller på och suddar tavlan. Han tänker istället använda sig av bägge sina pennor. Alla vet ju att det går utmärkt att läsa två olika idéer som tar upp samma yta på en tavla, så länge idéerna är nertecknade i olika färger.

Figure 1: Hosuja är en erfaren föreläsare.

Tavlan har han delat in i $R$ rader och $C$ kolumner, där $1 \leq R \times C \leq 1000$. Det finns totalt $1 \leq N \leq 1000$ idéer, numrerade från $1$ till $N$ enligt ordningen de ska presenteras i. Varje idé måste uttryckas på en enda rad, och för alla $1 \leq i \leq N$ gäller att idé nummer $i$ kräver $a_ i$ kolumner för att presentera. För varje idé måste Hosuja nu bestämma sig för om han vill använda den röda eller den blåa pennan.

När Hosuja presenterar kommer han att skriva upp idéerna i vanlig läsordning. Det vill säga, han börjar högst upp på tavlan vänsterifrån. Om det inte finns plats kvar på den nuvarande raden han skriver på för hela nästa idé, kommer han att byta rad och aldrig återgå igen till denna rad med färgen han använder just nu. Varje gång han byter färg kommer han att fortsätta där han slutade då han senast använde denna färgen. Han får byta färg mellan idéer, och får göra det så ofta han vill.

Nu undrar han hur många idéer han hinner skriva ner innan han tvingas sudda tavlan, givet att han väljer en optimal uppdelning av färger för idéerna.

Indata

På den första raden står talen $N$, antalet idéer, och talen $R$ och $C$, antalet rader och kolumner tavlan är indelad i. Därefter följer en rad med de $N$ talen $a_1, a_2, ..., a_ N$, där $1 \leq a_ i \leq C$ beskriver antalet kolumner som idé nummer $i$ behöver för att presenteras för alla $1 \leq i \leq N$.

Utdata

Skriv ett enda tal: Antalet idéer Hosuja hinner presentera innan han blir tvungen att sudda tavlan.

Poängsättning

Din lösning kommer att testas på olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av testfall 2

Figure 2: Om han väljer ordningen på färger R,B,R,RB,B kan han få plats med de första $6$ idéerna på tavlan om han gör som bilden visar.

5 1 4
1 2 3 2 1

4

8 2 10
8 1 2 10 9 9 2 4

6