T-shirts

Under PO-finalen får varje av de $N$ deltagarna en t-shirt. Domarna har dock en tendens att vara lite stressade med sistaminutenändringar till problemen (men bara ändringar – domarna väntar aldrig till dagen innan tävlingen med att göra ett nytt problem).

Detta betyder att när domarna beställer t-shirts kanske de inte tittar jättenoga på vilka t-shirtstorlekar deltagarna har. När allt kommer omkring, vem kan faktiskt skilja på en XS-t-shirt och en XL-t-shirt. Domarna kan det uppenbarligen inte, men det verkar som att de tävlanden kan när de sätter på sig sina nya t-shirts. Eftersom domarna aldrig lär sig att planera ordentligt kommer detta säkerligen vara ett problem nästa år också. Men just nu är det ditt problem.

Varje tävlanden har en föredragen storlek, men de kan faktiskt ha t-shirts i ett visst interval av storlekar. Mer specifikt kan den $i$:te tävlanden (noll-indexerat) bära en t-shirt som har minst storlek $L[i]$ och högst storlek $H[i]$ (båda gränser inklusive). Här har varje storlek blivit tilldelat ett heltal, så att ett större tal innebär en större storlek. Din uppgift är att tilldela t-shirts till deltagarna, så att så många deltagare som möjligt får en t-shirt som hen kan ha på sig. Domarna har beställt exakt $N$ t-shirts, och storleken på den $i$:te t-shirten är $T[i]$.

Exempel

Vi har $N = 3$ deltagare. Den första deltagaren kan ha t-shirts i storlekar mellan $3$ och $7$, den andra i storlekar mellan $3$ och $5$, och den sista tävlanden kan bara ha en t-shirt av storlek $6$.

De tre t-shirtarna har storlekarna $4, 6, 8$. Eftersom ingen kan bära den sista t-shirten kan högst två tävlanden få t-shirts. Vi kan också tilldela så många t-shirts, till exempel genom att ge den första t-shirten (storlek $4$) till den första tävlanden, och den andra t-shirten (storlek $6$) till den sista tävlanden. Svaret är således 2.

Uppgift

Din uppgift är att beräkna det maximala antalet deltagare som kan få en t-shirt som hen kan ha på sig. Du ska implementera funktionen tshirt(N, L, H, T).

• tshirt(N, L, H, T) - denna funktion kommer anropas exakt en gång av domaren.

  • N: ett heltal - antalet tävlanden (och t-shirts).

  • L: en array med $N$ heltal. L[i] ($0 \le i < N$) är den minsta storleken den $i$:te tävlanden kan ha på sig.

  • H: en array med $N$ heltal. H[i] ($0 \le i < N$) är den största storleken den $i$:te tävlanden kan ha på sig.

  • T: en array med $N$ heltal. H[i] ($0 \le i < N$) är storleken på den $i$:te t-shirten.

  • $0 \le L[i] \le H[i] \le \max (T)$, där $\max (T)$ betecknar det största värdet i arrayen $T$.

  • Funktionen ska returnera ett heltal - det största antalet tävlanden som kan få en t-shirt tilldelad till sig.

Ett kodskelett som innehåller funktionen du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/tshirts.zip.

Delpoäng

Uppgiften består av ett antal grupper. Varje grupp ger ett visst antal poäng, och för att klara gruppen måste du klara samtliga testfall i gruppen.

Låt $J$ vara antalet anrop till jump och $S$ antalet anrop till score.

Indataformat

Exempeldomaren läser indata i följande format:

• rad 1: N

• rad 2: L[0] L[1] ... L[N - 1]

• rad 3: H[0] H[1] ... H[N - 1]

• rad 4: T[0] T[1] ... T[N - 1]

Utdataformat

Exempeldomaren skriver ut en enda rad med returvärdet av tshirt(N, L, H, T).

3
3 3 6
7 5 6
4 6 8

2