Scrambled Scrabble

시간 제한1초메모리 제한2048 MB

요약

주어진 문자열에서 글자를 골라 음절(자음-모음-자음)을 최대한 많이 만들 때, 만들 수 있는 단어의 최대 길이를 구한다. Y는 자음과 모음 모두 가능하고 NG는 한 자음으로 쓸 수 있다.

난이도: 보통10점 중 5점
유형: 그리디, 수학
정답자: 아직 제출이 없습니다

문제

You are playing a word game using a standard set of $26$ uppercase English letters: A-Z. In this game, you can form vowels and consonants as follows.

The letters A, E, I, O, and U can only form a vowel.
The letter Y can form either a vowel or a consonant.
Each of the remaining letters other than A, E, I, O, U, and Y can only form a consonant.
The string NG can form a single consonant when concatenated together.

Denote a syllable as a concatenation of a consonant, a vowel, and a consonant in that order. A word is a concatenation of one or more syllables.

You are given a string $S$ and you want to create a word from it. You are allowed to delete zero or more letters from $S$ and rearrange the remaining letters to form the word. Find the length of the longest word that can be created, or determine if no words can be created.

입력

A single line consisting of a string $S$ ( $1 ≤ |S| ≤ 5000$ ). The string $S$ consists of only uppercase English letters.

출력

If a word cannot be created, output $0$ . Otherwise, output a single integer representing the length of longest word that can be created.

예제5

예제 1
입력
```
ICPCJAKARTA
```
예상 출력
```
9
```
예제 2
입력
```
NGENG
```
예상 출력
```
5
```
예제 3
입력
```
YYY
```
예상 출력
```
3
```
예제 4
입력
```
DANGAN
```
예상 출력
```
6
```
예제 5
입력
```
AEIOUY
```
예상 출력
```
0
```