시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB82028021536.689%

문제

백승환와 이석원은 한 팀이 되어 English 끝말대회에 출전했다. 앞단어의 마지막 글자가 뒷단어의 처음 글자와 같도록 단어를 차례대로 늘어놓는 게임 말이다. 단어는 주어지는 사전에 나와 있는 단어만 사용해야 하며 (영혼이 맑아질 만한 사실을 한 가지 가르쳐 주자면) 사전의 단어들은 모두 모음(A, E, I, O, U)으로만 이루어져있다는 것이다. 단어의 시작은 어떤 단어이든지 상관이 없고 같은 단어가 두 번 이상 사용되면 안 되며 게임에 사용된 단어의 길이의 합이 그 팀의 점수가 된다.

점수가 최대가 되도록 끝말잇기 규칙에 맞게 단어를 늘어놓는 프로그램을 만들어 승환이와 석원이를 도와주도록 하자.

입력

첫 줄에 사전에 포함된 단어 개수 N이 입력된다. (1 ≤ N ≤ 16)

두 번째 줄부터 N+1번째 줄까지 사전에 포함된 단어들이 한 줄에 하나씩 입력된다. 단어는 대문자 A, E, I, O, U로만 이루어져 있고 하나의 단어는 그 길이가 100을 넘지 않는다. 같은 단어가 두 번 주어지지 않는다.

출력

한 줄에 단어를 잘 늘어 놨을 때 얻을 수 있는 최대 점수를 출력한다.

예제 입력 1

3
AEIOU
UIU
EO

예제 출력 1

8

예제 입력 2

4
AEEEO
OEOAEEE
AO
O

예제 출력 2

13

예제 입력 3

5
IOO
IUUO
AI
OIOOI
AOOI

예제 출력 3

16
W3sicHJvYmxlbV9pZCI6IjIzMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwNWRcdWI5ZDBcdWM3ODdcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmMzMVx1YzJiOVx1ZDY1OFx1YzY0MCBcdWM3NzRcdWMxMWRcdWM2ZDBcdWM3NDAgXHVkNTVjIFx1ZDMwMFx1Yzc3NCBcdWI0MThcdWM1YjQgRW5nbGlzaCBcdWIwNWRcdWI5ZDBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjZDljXHVjODA0XHVkNTg4XHViMmU0LiBcdWM1NWVcdWIyZThcdWM1YjRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWI0YjdcdWIyZThcdWM1YjRcdWM3NTggXHVjYzk4XHVjNzRjIFx1YWUwMFx1Yzc5MFx1YzY0MCBcdWFjMTlcdWIzYzRcdWI4NWQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWIyOThcdWM1YjRcdWIxOTNcdWIyOTQgXHVhYzhjXHVjNzg0IFx1YjlkMFx1Yzc3NFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHViMDk4XHVjNjQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5Y2MgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCAoXHVjNjAxXHVkNjNjXHVjNzc0IFx1YjlkMVx1YzU0NFx1YzljOCBcdWI5Y2NcdWQ1NWMgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVhYzAwXHViOTc0XHVjY2QwIFx1YzhmY1x1Yzc5MFx1YmE3NCkgXHVjMGFjXHVjODA0XHVjNzU4IFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYWE4XHVjNzRjKEEsIEUsIEksIE8sIFUpXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM3NDAgXHVjNWI0XHViNWE0IFx1YjJlOFx1YzViNFx1Yzc3NFx1YjRlMFx1YzljMCBcdWMwYzFcdWFkMDBcdWM3NzQgXHVjNWM2XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWIyZThcdWM1YjRcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjMGFjXHVjNmE5XHViNDE4XHViYTc0Jm5ic3A7XHVjNTQ4IFx1YjQxOFx1YmE3MCBcdWFjOGNcdWM3ODRcdWM1ZDAgXHVjMGFjXHVjNmE5XHViNDFjIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWRmOCBcdWQzMDBcdWM3NTggXHVjODEwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODEwXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHViMDVkXHViOWQwXHVjNzg3XHVhZTMwIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHViMmU4XHVjNWI0XHViOTdjIFx1YjI5OFx1YzViNFx1YjE5M1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YzY0MCBcdWMxMWRcdWM2ZDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOGZjXHViM2M0XHViODVkIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjMGFjXHVjODA0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWIyZThcdWM1YjQgXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxNik8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWIzMDBcdWJiMzhcdWM3OTAgQSwgRSwgSSwgTywgVVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIyZThcdWM1YjRcdWIyOTQgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWI0NTAgXHViYzg4IFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjIFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzk4IFx1YjI5OFx1YzViNCBcdWIxYThcdWM3NDQgXHViNTRjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzMjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXT1JEUyIsImRlc2NyaXB0aW9uIjoiPHA+SW8gYW5kIEFvIGFyZSBwbGF5aW5nIGEgd29yZCBnYW1lLiBUaGV5IGFsdGVybmF0ZWx5IHNheSB3b3JkcyBjb25zaXN0aW5nIG9mIHZvd2VscyBvbmx5IHNvIHRoYXQgdGhlIGZpcnN0IGxldHRlciBvZiBldmVyeSBuZXcgd29yZCBpcyB0aGUgc2FtZSBhcyB0aGUgbGFzdCBsZXR0ZXIgb2YgdGhlIHByZXZpb3VzIHdvcmQuIEEgZ2FtZSBjYW4gc3RhcnQgd2l0aCBhbnkgd29yZC48XC9wPlxyXG5cclxuPHA+SXQgaXMgZm9yYmlkZGVuIHRvIHNheSBhbnkgd29yZCB0d2ljZS4gT25seSB3b3JkcyBmcm9tIGdpdmVuIGRpY3Rpb25hcnkgY2FuIGJlIHVzZWQgaW4gYSBnYW1lLjxcL3A+XHJcblxyXG48cD5BIGNvbXBsZXhpdHkgb2YgYSBnYW1lIGlzIGRlZmluZWQgYXMgYSBzdW0gb2YgbGVuZ3RocyBvZiBhbGwgdGhlIHNwb2tlbiB3b3JkcyBkdXJpbmcgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBtYXhpbWFsIHBvc3NpYmxlIGNvbXBsZXhpdHkgb2YgYSBnYW1lIHRoYXQgY2FuIGJlIHBsYXllZCB1c2luZyB3b3JkcyBmcm9tIGEgZ2l2ZW4gZGljdGlvbmFyeS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZpbGUgY29udGFpbnMgYSBuYXR1cmFsIG51bWJlciBOLCAxICZsZTsgTiAmbGU7IDE2LCB0aGUgbnVtYmVycyBvZiB3b3JkcyBpbiBhIGRpY3Rpb25hcnkuIEVhY2ggb2YgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIG9uZSB3b3JkIGZyb20gYSBkaWN0aW9uYXJ5LiBBIHdvcmQgaXMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzICZsc3F1bztBJnJzcXVvOywgJmxzcXVvO0UmcnNxdW87LCAmbHNxdW87SSZyc3F1bzssICZsc3F1bztPJnJzcXVvOyBhbmQgJmxzcXVvO1UmcnNxdW87LiBMZW5ndGggb2YgZXZlcnkgd29yZCB3aWxsIGJlIDEwMCBvciBsZXNzLiBBbGwgdGhlIHdvcmRzIHdpbGwgYmUgZGlmZmVyZW50LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHRoZSBtYXhpbWFsIHBvc3NpYmxlIGNvbXBsZXhpdHkgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2001 > Croatian Olympiad in Informatics 2001 2번

  • 문제의 오타를 찾은 사람: chogahui05
  • 빠진 조건을 찾은 사람: jh05013