# Problem: Medusa's Snakes

Want to try solving this problem? You can submit your code online if you log in or register.

## Medusa's Snakes

**Input File:** `snakein.txt`
**Output File:** `snakeout.txt`
**Time Limit:** 1 second

**Memory Limit:** 1 GB

After the success of your latest research project in mythical DNA, you have gained the attention of a most diabolical creature: Medusa.

Medusa has snakes instead of hair. Each of her snakes' DNA is represented by an uppercase
string of letters. Each letter is one of `S`, `N`, `A`, `K` or `E`.

Your extensive research shows that a snake's venom level depends on its DNA. A snake has
venom level x if its DNA:

- has exactly 5x letters
- begins with x copies of the letter
`S`
- then has x copies of the letter
`N`
- then has x copies of the letter
`A`
- then has x copies of the letter
`K`
- ends with x copies of the letter
`E`.

For example, a snake with venom level 1 has DNA `SNAKE`, while a snake that has venom level 3 has DNA `SSSNNNAAAKKKEEE`. If a snake's DNA does not fit the format described above, it has a venom level of 0.

Medusa would like your help making her snakes venomous, by **deleting zero or more letters** from their DNA. Given a snake's DNA, can you work out the maximum venom level this snake could have?

### Input

The first line contains the integer

N: the number of letters in the snake's DNA. The second line contains a string of

N uppercase letters, representing the snake's DNA. Each letter is one of

`S`,

`N`,

`A`,

`K` or

`E`.

### Output

Your program should output a single integer: the maximum venom level the snake could have,
after you delete some (possibly none) of the letters from its DNA.

### Sample Input 1

17
KSEESNANNAAKNKESE

### Sample Output 1

2

### Sample Input 2

22
SSSSNNNAAAAKKKKEEEEEEE

### Sample Output 2

3

### Sample Input 3

15
SNAKESNAKESNAKE

### Sample Output 3

1

### Sample Input 4

6
KANSAS

### Sample Output 4

0

### Explanation

The letters that are deleted in each case are underlined below:

- Sample Input 1:
__K__S__EE__SN__A__N__N__AAK__N__KE__S__E → `SSNNAAKKEE`.
- Sample Input 2:
`SSS`__S__NNNAAA__AK__KKKEE__EEE__E__E__ → `SSSNNNAAAKKKEEE`.
- Sample Input 3:
__SNAKE__SNA__KESNA__KE → `SNAKE`.
- Sample Input 4: No matter which letters you delete, the snake will always have venom level 0, so the answer is 0.

### Subtasks & Constraints

For all cases, 5 ≤ N ≤ 100,000. Additionally:

- For Subtask 1 (15 marks), all
`S` come before all `N`, which come before all `A`, which come before
all `K`, which come before all `E`. There will be at least one of each letter. Sample Input 2 is an example of a case that could be in this subtask.
- For Subtask 2 (15 marks), the DNA sequence consists of
`SNAKE` repeated some number of
times. Sample Input 3 is an example of a case that could be in this subtask.
- For Subtask 3 (30 marks), N ≤ 10.
- For Subtask 4 (20 marks), N ≤ 1000.
- For Subtask 5 (20 marks), no further constraints apply.