Lukáša už nebavilo papať Julkine uhorky. Žiaľ, tieto vzťahové problémy boli neudržateľné a tak sa Lukáš a Julka rozišli. Lukáš však neváhal a s nadobudnutou skúsenosťou s prvým vzťahom začal baliť dalšie ženy. Je však taký dobrý, že nestíha si s každou zatelefónovať na dobrú noc. Pomôž mu vyrobiť si rozpis tak, aby žiadna žena nebola sklamaná.

Úloha

Lukáš má $k$ “kamarátok”, a $i$-ta kamarátka s ním môžem volať v časovom intervale $\left< s_i, e_i \right)$. To znamená, že $i$-ta kamarátka s Lukášom volá od času $s_i$ vrátane, až po posledný moment pred $e_i$. S jednou kamarátkou buď volá celý čas, čo s ňou volať môže, alebo s ňou nevolá vôbec. Veľa kamarátok by s ním však chcelo naraz telefónovať, a tak sa Lukáš celkovo snaži zavolať si s čo najviac kamarátkami. V sade $1$ a $2$ môže vždy volať s iba jednou kamarátkou v jednom čase. Neskôr však Lukáš chcel volať s ešte viac kamarátkami naraz a tak nakódil masívny gigachad filter (keďže Lukáš sám gigachadom je). Cez neho necháva jeho kamarátky sa rozprávať medzi sebou, dokonca až $r$ kamarátiek naraz. Teraz potrebuje vedieť, s najviac koľkými kamarátkami si zvláda zavolať, ak vie v jednom čase volať s $\leq r$ kamarátkami.

Formát vstupu

Na vstupe sú na prvom riadku tri čísla $s, k, r$, označujúce v tomto poradí číslo sady, počet Lukášových kamarátiek a počet, s koľkými kamarátkami naraz Lukáš môže volať. Následuje $k$ riadkov po dvoch racionálnych číslach na najviac dve desatinné miesta $s_i,e_i$ (teda v jazykoch ako c alebo java potrebuješ použiť typ float), ktoré udávajú časový interval $\left< s_i, e_i \right)$, kedy si $i$-ta kamarátka chce s lukášom volať.

Obmedzenia na vstupe

Zároveň môžeš predpokladať, že v 3. sade platí vždy $r = 2$.

Formát výstupu

Na výstupe vráť jedno číslo $m$ - najväčší počet kamarátok, s ktorými si dnes večer Lukáš môže zavolať.

Príklad

0 5 1
4 5.2
0.5 2
2.5 7
1 3.2
0 4.7

2

Môže najprv volať s 4. kamarátkou do času 3.2 a potom s 1. kamarátkou do času 5.2. Podobne môže najprv volať s 2. kamarátkou a potom s 1. kamarátkou alebo s 2. kamarátkou a potom s 3. kamarátkou.

0 5 2
4 5.2
0.5 2
2.5 7
1 3.2
0 4.7

4

Môže najprv volať “jednou rukou” s 4. kamarátkou do času 3.2 a potom s 1. kamarátkou do času 5.2. Zároveň volá “druhou rukou” s 2. kamarátkou do času 2 a potom s 3. kamarátkou do času 7.