시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 354 100 73 30.672%

문제

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

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

입력

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

출력

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

예제 입력 1

3
AEIOU
UIU
EO

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjIzMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwNWRcdWI5ZDBcdWM3ODdcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmMzMVx1YzJiOVx1ZDY1OFx1YzY0MCBcdWM3NzRcdWMxMWRcdWM2ZDBcdWM3NDAgXHVkNTVjIFx1ZDMwMFx1Yzc3NCBcdWI0MThcdWM1YjQgRW5nbGlzaCBcdWIwNWRcdWI5ZDBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjZDljXHVjODA0XHVkNTg4XHViMmU0LiBcdWM1NWVcdWIyZThcdWM1YjRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWI0YjdcdWIyZThcdWM1YjRcdWM3NTggXHVjYzk4XHVjNzRjIFx1YWUwMFx1Yzc5MFx1YzY0MCBcdWFjMTlcdWIzYzRcdWI4NWQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWIyOThcdWM1YjRcdWIxOTNcdWIyOTQgXHVhYzhjXHVjNzg0IFx1YjlkMFx1Yzc3NFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHViMDk4XHVjNjQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5Y2MgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCAoXHVjNjAxXHVkNjNjXHVjNzc0IFx1YjlkMVx1YzU0NFx1YzljOCBcdWI5Y2NcdWQ1NWMgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVhYzAwXHViOTc0XHVjY2QwIFx1YzhmY1x1Yzc5MFx1YmE3NCkgXHVjMGFjXHVjODA0XHVjNzU4IFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYWE4XHVjNzRjKEEsIEUsIEksIE8sIFUpXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM3NDAgXHVjNWI0XHViNWE0IFx1YjJlOFx1YzViNFx1Yzc3NFx1YjRlMFx1YzljMCBcdWMwYzFcdWFkMDBcdWM3NzQgXHVjNWM2XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWIyZThcdWM1YjRcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjMGFjXHVjNmE5XHViNDE4XHViYTcwIFx1YzU0OCBcdWI0MThcdWJhNzAgXHVhYzhjXHVjNzg0XHVjNWQwIFx1YzBhY1x1YzZhOVx1YjQxYyBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFkZjggXHVkMzAwXHVjNzU4IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHVjODEwXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHViMDVkXHViOWQwXHVjNzg3XHVhZTMwIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHViMmU4XHVjNWI0XHViOTdjIFx1YjI5OFx1YzViNFx1YjE5M1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YzY0MCBcdWMxMWRcdWM2ZDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOGZjXHViM2M0XHViODVkIFx1ZDU1OFx1Yzc5MC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjJlOFx1YzViNCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIChOICZsZTsgMTYpPGJyIFwvPlxyXG4mbmJzcDsgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWIzMDBcdWJiMzhcdWM3OTAgQSwgRSwgSSwgTywgVVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIyZThcdWM1YjRcdWIyOTQgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc5OCBcdWIyOThcdWM1YjQgXHViMWE4XHVjNzQ0IFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzMjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXT1JEUyIsImRlc2NyaXB0aW9uIjoiPHA+SW8gYW5kIEFvIGFyZSBwbGF5aW5nIGEgd29yZCBnYW1lLiBUaGV5IGFsdGVybmF0ZWx5IHNheSB3b3JkcyBjb25zaXN0aW5nIG9mIHZvd2VscyBvbmx5IHNvIHRoYXQgdGhlIGZpcnN0IGxldHRlciBvZiBldmVyeSBuZXcgd29yZCBpcyB0aGUgc2FtZSBhcyB0aGUgbGFzdCBsZXR0ZXIgb2YgdGhlIHByZXZpb3VzIHdvcmQuIEEgZ2FtZSBjYW4gc3RhcnQgd2l0aCBhbnkgd29yZC48XC9wPlxyXG5cclxuPHA+SXQgaXMgZm9yYmlkZGVuIHRvIHNheSBhbnkgd29yZCB0d2ljZS4gT25seSB3b3JkcyBmcm9tIGdpdmVuIGRpY3Rpb25hcnkgY2FuIGJlIHVzZWQgaW4gYSBnYW1lLjxcL3A+XHJcblxyXG48cD5BIGNvbXBsZXhpdHkgb2YgYSBnYW1lIGlzIGRlZmluZWQgYXMgYSBzdW0gb2YgbGVuZ3RocyBvZiBhbGwgdGhlIHNwb2tlbiB3b3JkcyBkdXJpbmcgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBtYXhpbWFsIHBvc3NpYmxlIGNvbXBsZXhpdHkgb2YgYSBnYW1lIHRoYXQgY2FuIGJlIHBsYXllZCB1c2luZyB3b3JkcyBmcm9tIGEgZ2l2ZW4gZGljdGlvbmFyeS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZpbGUgY29udGFpbnMgYSBuYXR1cmFsIG51bWJlciBOLCAxICZsZTsgTiAmbGU7IDE2LCB0aGUgbnVtYmVycyBvZiB3b3JkcyBpbiBhIGRpY3Rpb25hcnkuIEVhY2ggb2YgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIG9uZSB3b3JkIGZyb20gYSBkaWN0aW9uYXJ5LiBBIHdvcmQgaXMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzICZsc3F1bztBJnJzcXVvOywgJmxzcXVvO0UmcnNxdW87LCAmbHNxdW87SSZyc3F1bzssICZsc3F1bztPJnJzcXVvOyBhbmQgJmxzcXVvO1UmcnNxdW87LiBMZW5ndGggb2YgZXZlcnkgd29yZCB3aWxsIGJlIDEwMCBvciBsZXNzLiBBbGwgdGhlIHdvcmRzIHdpbGwgYmUgZGlmZmVyZW50LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHRoZSBtYXhpbWFsIHBvc3NpYmxlIGNvbXBsZXhpdHkgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d