Prihlásenie Registrácia  

SVK-P - Parašutisti

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Herný priemysel má za sebou dlhý vývoj. Začiatkom 90-tych rokov boli v našom regióne veľmi populárne digitálne hry (najmä ruskej produkcie). Jedna z nich mala názov Parašutisti. Myšlienka hry bola jednoduchá. Vrtuľník zhadzoval parašutistov nad riekou plnou pažravých rýb. Aby parašutista prežil, nesmel pristáť vo vode. Na rieke plával čln, ktorý zachraňoval parašutistov pred pádom do vody. Čln bol ovládaný hráčom. Za každého zachráneného parašutistu bol jeden bod. Ak traja parašutisti skončili vo vode (t.j. nepristáli v člne), hra končila.

Parašutisti

Technické možnosti vtedajšej doby sa prejavili aj v hrách. Napríklad čln sa mohol nachádzať len na niekoľkých pozíciach. Hra prebiehala v diskrétnych časových krokoch. V rámci každého kroku sa loď mohla posunúť o jednu pozíciu vľavo alebo vpravo (alebo ostala stáť na mieste). Nuž a ani tie generátory náhodných čísel (určujúce kedy a kam parašutista dopadne) neboli vždy super náhodné.

Úloha

Poznáme časy a pozície dopadov jednotlivých parašutistov. Vytvorte program, ktorý vypočíta koľko najviac bodov môžeme získať. Upozorňujeme, že hra končí akonáhle nezachránime určený počet parašutistov.

Vstup

Prvý riadok obsahuje trojicu medzerou oddelených čísel N, M a K, kde N (1 ≤ N ≤ 50000) je počet parašutistov, M (1 ≤ M ≤ 100) je počet pozícii člna a K (1 ≤ K ≤ 60) je počet nezachránených parašutistov, pri ktorom končí hra. Jednotlivé pozície člnu sú číslované od 0 po M-1. Ďalej bude nasledovať N riadkov popisujúcich pristátia jednotlivých parašutistov. Každý riadok obsahuje dvojicu medzerou oddelených čísel T (1 ≤ T ≤ 1000000) a P (0 ≤ P ≤ M-1). Číslo T určuje čas (počet diskrétnych časových krokov od začiatku hry), kedy parašutisti dopadá na hladinu. Číslo P určuje polohu, v ktorej sa parašutista pri dopade nachádza. Parašutisti sú na vstupe usporiadaný podľa času dopadu. V jednom čase môže dopadnúť aj viacero parašutistov.

Výstup

Vypíšte maximálny počet bodov (zachránených parašutistov), ktorý je možné získať.

Príklad

Vstup:

40 30 4
63 27
86 9
188 17
293 0
334 3
384 17
413 15
426 5
512 29
614 15
648 29
675 2
728 14
833 3
848 1
915 15
1017 5
1113 6
1150 2
1177 0
1180 4
1280 10
1348 11
1441 6
1452 26
1513 26
1521 6
1533 14
1566 25
1652 25
1751 0
1793 26
1813 5
1833 0
1899 21
1972 4
2007 14
2046 26
2096 8
2102 20

Výstup:

29