Bit Monkey

Cerință

Ești o maimuță formată din unuri și zerouri, iar că orice maimuță tu ai ca scop un singur lucru: să ajungi la o banană, bineînțeles în cazul tău o banană virtuală. Fructul se află la vârful unui stâlp virtual care are mai multe bare virtuale pe stânga sau pe dreapta lui. Tu, ca maimuță virtuală, ai anvergura brațelor maxim $K$, asta înseamnă că distanța dintre două bare pe care le vei ține o să fie mai mică sau egală ca acest $K$.

Barele de pe stânga pot fi apucate doar cu mâna stângă și asemenea pentru cele de pe dreapta. Nu poți apuca o bară de pe dreapta cu mâna stângă sau invers. Fiecare bară are o dificultate, iar tu, ca maimuță virtuală leneșă, poți să sari peste unele dintre ele. Totuși, te întrebi care este cea mai dificilă bară pe care trebuie să o iei pentru a ajunge la banană virtuală.

Cum toată lumea știe că maimuțele virtuale știu să codeze scrie un cod care să îți calculeze răspunsul.

Tu începi cu ambele mâini la înălțime $0$ ținâdu-te de baza stâlpului virtual. Dacă nu se poate ajunge în vârf se va afișa $-1$. Se consideră că ai ajuns în vârf dacă ai putea ajunge la înalțimea $N+1$ cu oricare dintre mâini. Se poate considera că la înalțimile $0$ și $N+1$ ai câte o bară de dificultate 0 care poate fi apucată cu ambele mâini.

Date de intrare

Stâlpul are o înălțime $N$, și la fiecare unitate o să fie o bară pe stânga sau pe dreapta cu dificultatea $X$.
Pe prima linie o să apară variabilele $N$ și $K$ separate printr-un spațiu, iar pe următoarele $N$ rânduri descrierea barelor de forma: $P$ (caracterul S, sau D, reprezentând stânga sau dreapta), $X$ (dificultatea).

Date de ieșire

Raspunsul va trebui să fie un singur număr $R$, fiind răspunsul problemei.

Restricții și precizări

• $1 \leq N, K \leq 10^6$
• $1 \leq X \leq 10^9$

Exemplu

stdin

10 4
D 1
D 2
S 7
S 4
D 1
D 4
S 9
S 3
S 8
D 5

stdout

4

Explicație

Sunt mai multe soluții posibile, dar o ordine posibila de a apuca bările este: mâna dreaptă la înalțimea $2$, stânga la $4$, dreapta la $6$, stânga la $8$, iar cu dreapta poți ajunge la $N + 1$, deci poți ajunge la banană. Răspunsul este deci $4$ pentru că nu se poate gasi un traseu in care bara maximă este mai mică de $4$.