410202: GYM103973 L Phigros

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Phigrostime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

An integer indicating the maximum score Walk Alone could get.

ExamplesInput
6 5
perfect
good
perfect
bad
good
Output
695000
Input
1000 2
miss
good
Output
998685
Note

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

加入题单

上一题 下一题 算法标签: