Problem F
Fiskspelet

Du spelar fiskspelet. Du är en fisk som ska äta mindre fiskar men aldrig får bli uppäten av större fiskar. Fiskarna ändrar aldrig storlek. Du får poäng för varje fisk du äter och självklart vill du ha så mycket poäng som möjligt.

Spelplanen kan ses som ett rutnät med $h$ rader (numrerade från 1 till $h$) men obegränsat antal kolumner. Du befinner dig i kolumnen $x=0$ och kan bara röra dig vertikalt (uppåt och nedåt). De andra fiskarna rör sig däremot aldrig vertikalt utan börjar i en viss kolumn $x>0$ och flyter med konstant fart åt vänster (mot din kolumn).

Alla fiskar (även du) har bredden 1 ruta. Din höjd är 7. Det finns tre andra sorters fiskar: "liten" med höjd 3, "mellan" med höjd 5 och "stor" med höjd 9. Fiskarna har olika hastigheter. Varje sekund kan du röra dig en ruta uppåt eller nedåt (eller stå stilla). På samma tid rör sig en liten fisk 1 ruta, en mellanfisk 2 rutor och en stor fisk 3 rutor åt vänster. Du väljer själv på vilken höjd-nivå din fisk ska börja, men observera att hela fisken alltid måste vara inom spelplanen.

En fisk kan äta fiskar som är mindre än den själv. Du kan alltså äta fiskar av storlek 3 och 5, och får då 10 respektive 20 poäng. Men fiskar av höjd 9 kommer att äta upp dig, och du måste akta dig för dem. Skulle du bli uppäten förlorar du. För att det inte ska bli orättvist vem som äter vem så har sjöjungfrun Arashiel bestämt att följande sker i varje diskret sekundsteg:

1. Du gör ditt drag (flyttar upp, ner, eller stannar kvar).

2. Stora fiskar avancerar tre steg, mellan-fiskar avancerar två steg och små fiskar avancerar ett steg.

3. Stora fiskar äter mellan- och småfiskar (eller dig) om de är i samma kolumn och överlappar vertikalt (minst en ruta gemensam).

4. Mellanfiskar som överlevt äter småfiskar om de är i samma kolumn och överlappar vertikalt.

5. Du äter små- och mellanfiskar om de är i din kolumn ($x=0$) och överlappar vertikalt.

Situationen i första exemplet. De heldragna färgade rektanglarna visar fiskarnas utgångspositioner och de streckade rektanglarna visar deras positioner efter 4 respektive 8 sekunder. Den svarta rektangeln visar en av flera optimala utgångspositioner för dig. I detta fall kan du helt enkelt stå stilla och invänta den gröna mellanfisken.

Situationen i andra exemplet. Den svarta rektangeln visar var du måste befinna dig vid tiden $t=4$ sekunder när du äter den blå lilla fisken (det går bra att även ha detta som utgångsposition). Den delade rutan markerar att fiskarna överlappar på denna ruta. Sedan måste du röra dig i full fart uppåt för att kunna äta den gröna mellanfisken vid $t=11$ (din position visas då av den grå streckade rektangeln). Slutligen måste du fortsätta uppåt för att undkomma den röda stora fisken som når din kolumn vid $t=14$ (detta skulle bli för kladdigt att visa i figuren).

Indata

På första raden står två heltal, $1 \leq n \leq 50\, 000$ och $20 \leq h \leq 1\, 000$, antalet fiskar samt höjden på banan. Sedan följer $n$ rader, en för varje fisk. På varje rad står först en bokstav, L/M/S, alltså om fisken är liten, mellan eller stor. Därefter följer kolumnen $x$ som fisken startar på ($2 \leq x \leq 10^{16}$), samt vilken rad $y$ som utgör fiskens mellersta ruta (alltid vald så att hela fisken får plats inom intervallet $[1, h]$). De tre värdena åtskiljs med blanksteg.

Dessutom gäller att:

• Inga fiskar i indata kommer överlappa varken helt eller delvis (initialt).

• $x$-koordinaten för varje fisk kommer alltid att vara jämn. För den större fiskstorleken kommer den även alltid att vara delbar med 3. Detta eftersom vi vill att alla krockar ska ske på heltalskoordinater.

• Du kommer alltid kunna klara dig från att bli uppäten, dvs spelet har alltid en lösning.

Utdata

Utdata ska bestå utav en rad med ett enda heltal, antalet poäng du får om du spelar spelet optimalt.

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

• För 20 delpoäng så gäller det att inga andra fiskar äter upp varandra, $n \leq 1\, 000$, $h \leq 50$, och x-koordinaterna är små ($\leq 10\, 000$). Observera att förutom i dessa testfall ryms x-koordinaterna oftast inte i 32-bitars heltal.

• För ytterligare 20 delpoäng så gäller det att inga andra fiskar äter upp varandra. $h \leq 50$.

• För ytterligare 30 delpoäng så gäller det att mellanfiskar aldrig äter småfiskar. $h \leq 50$.

• För ytterligare 20 delpoäng så gäller att höjden $h$ är $\leq 50$

3 20
L 4 2
S 30 8
M 20 18

20

3 20
L 4 2
S 42 8
M 22 18

30 

2 20
L 6 3
L 6 12

10

4 20
L 10 6
L 20 5
L 30 7
M 40 6

30

3 20
L 18 3
L 16 9
M 20 6

20

3 20
L 12345678901234 3
L 12345678901234 9
M 12345678901232 6

40

3 20
L 12345678901234 3
L 12345678901234 9
M 12345678901236 6

20