スキルチェックSKILL CHECK



つけ麺屋

あるつけ麺屋では、顔なじみになるにしたがって付け合わせの海苔の枚数が変わるという常連システムが存在するという。
顔なじみかどうかは店員の記憶のみに頼っているために、来店回数は店員ごとにそれぞれ独立に数えられる。
あなたは偶然にも明日からの店員のシフト表と、各店員が来店何回目の客に何枚の海苔をつけるかという情報を手に入れた。
つけ麺と海苔が大好きなあなたはできるだけ多くの海苔を食べたいが、健康上の理由で、つけ麺屋に通える回数には
上限があり、またつけ麺屋に通う間隔をある日数以上空けなければならないという制限がある。
海苔をより多く食べるために最適な通い方をした場合に、食べることのできる海苔の枚数を求めよ。

全体の日数をN、つけ麺屋に通える日数を M、次に通うまでに空けなければならない日数を I、店員のシフトを S、
店員Aが初めて来店した(店員Aが初めて見た)客につける海苔の枚数を A1、
来店2回目の客につける海苔の枚数を A2、
来店3回目の客につける海苔の枚数を A3、
来店4回目以降の客につける海苔の枚数を A4、
店員Bが来店1回目、2回目、3回目、4回目以降の客につける海苔の枚数をそれぞれ B1、B2、B3、B4、
店員Cが来店1回目、2回目、3回目、4回目以降の客につける海苔の枚数をそれぞれ C1、C2、C3、C4、
店員Dが来店1回目、2回目、3回目、4回目以降の客につける海苔の枚数をそれぞれ D1、D2、D3、D4、
店員Eが来店1回目、2回目、3回目、4回目以降の客につける海苔の枚数をそれぞれ E1、E2、E3、E4、
とすると入力は標準入力から次の形式で与えられます。

N M I S A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 D1 D2 D3 D4 E1 E2 E3 E4

各入力値は次の制約を満たすものとします。
1 <= N <= 100 0 <= M <= N 0 <= I <= N 文字列Sの長さはNで各文字は A, B, C, D, E のいずれか 0 <= Ai, Bi, Ci, Di, Ei <= 1000000

あなたが食べることのできる最大の海苔の枚数を標準出力に出力してください。
海苔の枚数はカンマや頭に0などをつけずに整数で出力してください。

入力1
30 10 2 ABCDEABCDEABCDEABCDEABCDEABCDE 2 3 4 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

出力1
26
店員Aがいる日に通い続け、最後だけ店員Dもしくは店員Eから2枚海苔をもらうのが最適
入力2
30 10 2 ABABAAABCCDDDEEEEEECEAABAAAABB 3 4 5 6 1 4 4 5 1 2 2 3 1 4 5 10 12 1 2 4
出力2
40
2日おきに通い続けるのが最適
また、次のように制約条件を変更した場合の実装も考えてください。
1 <= N <= 10000 M = N 0 <= I <= N 文字列Sの長さはNで各文字は A, B, C, D, E のいずれか 0 <= Ai, Bi, Ci, Di, Ei <= 10000

スキルチェックの解答(ソースコード)はエントリーフォームに添付してください。

また、解答方針についての説明や補足があれば、説明を記載したファイルも一緒に添付してご送付ください。