410202: GYM103973 L Phigros

Phigros is a music game in which players are required to touch the screen following the rhythm of songs and try to get the highest scores.

The total score of a song is the sum of the following two parts rounded to the nearest integer (assume that the song has $$$n$$$ notes in total):

• Accuracy. The accuracy score for each note is added up independently according to the judgment:
  • Perfect: $$$900\,000\cdot n^{-1}$$$;
  • Good: $$$585\,000\cdot n^{-1}$$$;
  • Bad or miss: $$$0$$$.

• Combo. The Max Combo of a song is the maximum number of continuous notes with perfect or good judgements. The combo score for a song with Max Combo $$$m$$$ is $$$100\,000 \,m\cdot n^{-1}$$$.

Recall that $$$$$$ \text{round}(x)=\begin{cases} \lfloor x\rfloor, & x<\lfloor x\rfloor+0.5 \\ \lfloor x\rfloor + 1, & x\ge\lfloor x\rfloor+0.5 \end{cases} $$$$$$

Now Walk Alone is playing a song with $$$n$$$ notes. He has already got the judgement of the first $$$k$$$ notes, and he wants to know the maximum score he could get if he played the rest of the song perfectly.

The first line contains two integers $$$n$$$ and $$$k\ (1\le k\le n\le 4000)$$$, the note count of the song and the number of notes Walk Alone has played.

The $$$i$$$-th of the following $$$k$$$ lines contains one of 'perfect', 'good', 'bad' and 'miss' (without quotes), indicating the judgement of the $$$i$$$-th note.

An integer indicating the maximum score Walk Alone could get.

6 5
perfect
good
perfect
bad
good

695000

1000 2
miss
good

998685

A song has at most $$$4000$$$ notes in Phigros.