問題文

パ研商店では、P, A, K, E, N, C, A, M, P の文字が書かれたパネル計 9 枚を 1 つのセットにして販売しています。(同じ文字のパネルが複数枚含まれていることに注意してください。)

パンダのパ太郎はこのセットをいくつか買い、買ったパネルのうち何枚かを選んでそれらを自由に並べることで長さ N の文字列 S を作りたいと考えています。

パ太郎が S を作るために買う必要があるセットの数の最小値を求めてください。

ただし、セットをいくつ買っても S を作ることができない場合はそのことを報告してください。またパ研商店の在庫は十分多いものとします。

制約

• 1 \leq N \leq 10^5
• S は英大文字からなる長さ N の文字列
• N は整数

入力例 1

7
PANCAKE

出力例 1

1

PANCAKE を作るためには P が 1 つ、 A が 2 つ、 N が 1 つ、 C が 1 つ、 K が 1 つ、 E が 1 つ必要です。セットを 1 セット買うことでこれらの文字を全て揃えることができます。

入力例 2

5
PEACE

出力例 2

2

入力例 3

5
IKAHO

出力例 3

-1