Phigros
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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: ;
    • Good: ;
    • 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 .

Recall that
    

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 , 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.
示例1

输入

复制
6 5
perfect
good
perfect
bad
good

输出

复制
695000
示例2

输入

复制
1000 2
miss
good

输出

复制
998685

备注:

A song has at most 4000 notes in Phigros.