Zadanie

Divoký západ

Počet bodov: 25

Kovboji na divokom západe to mali ťažké. Každý kôň cválal inou rýchlosťou, no keď išli v stáde, prispôsobili sa a stádo išlo priemernou rýchlosťou jednotlivích koní. Kovboji jedného dňa zistili, že keď koníky podkujú, môže sa im rýchlosť zmeniť. Nie každému koníkovi sa však podkovi páčia. Každý kovboj si teda zapísal akou rýclosťou cvála jeho koník, akú rýchlosť má keď ho podkuje, a či je koník smutný keď ho podkuje.

Kovboji by sa teraz potrebovali dostať do večera do susedného mesta a vyrátali si akú príemernú rýchlosť na to potrebujú mať.

Vašou úlohou je zistiť, koľko najmenej koníkov musí byť smutných na to aby kovboji svoju cestu stihli.

Vstup

Na prvom riadku sú dve celé čísla \(1 \leq N \leq 100~000\) - počet kovbojov a \(1 \leq X \leq 100\) - priemerná rýchlosť ktorú chcú kovboji dosiahnuť. Na ďaľších \(N\) riadkoch sú medzerou oddelené rýchlosť koníka bez podkov, rýchlosť koníka s podkovammi a slovo “ano” alebo “nie” podla toho či je koník smutný keď má podkovy.

Každá rýchlosť je celé číslo medzi \(1\) a \(100\).

V piatich sadách je \(N\) postupne do \(10\), \(100\), \(1000\), \(10000\), \(100000\).

Výstup

Na výstup vypíšte “neda sa” ak to kovboji za žiadnych okolností nestihnú, inak vypíšte jedno číslo - najmenší možný počet smutných koníkov, aby kovboji stihli cestu.

Príklad

Input:

3 12
5 10 ano
10 4 nie
3 7 nie

Output:

neda sa

Žiadny koník nevie ísť rýchlejšie ako 10, teda priemernú rýchllosť 12 nedosiahnu.

Input:

5 9
7 10 nie
8 2 ano
10 12 ano
3 8 ano
11 10 nie

Output:

1

Bez podkov je priemerná rýchlosť \(7.8\). Ak podkujeme prvého a štvrtého koníka, priemerná rýchlosť bude \(9.4\) pričom smutný bude len ten štvrtý koník.