시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 0 0 0.000%

문제

선영이는 테트리스 같은 게임을 하고 있다.

게임은 비어있는 세 열에서 시작한다. 게임이 진행되는 동안 글자가 하나씩 화면의 가장 위에 보여진다. 글자가 보여지면, 선영이는 세 열중 하나를 선택한다. 선택한 열이 비어있다면, 그 열의 가장 아래에 글자를 놓고, 비어있지 않다면, 그 열의 가장 위에 있는 단어의 위에 글자를 놓는다.

게임이 끝난 후에 선영이가 얻은 점수는 각 열의 점수의 합이다. 각 열의 점수는 다음과 같이 계산할 수 있다.

먼저, 동일한 단어로 이루어진 그룹을 모두 찾는다.

예를 들어, 어떤 열의 글자가 아래 그림과 같다고 하자.

위의 그림에는 총 4개의 그룹이 있다. 그 다음, 각 그룹의 크기(포함되어 있는 글자의 개수)에 따라서 점수를 계산하면 된다.

예를 들어, 크기가 1인 그룹은 3점, 2인 그룹은 7점, 3인 그룹은 5점이라고 한다면, 위의 그림은 5+3+5+7=20점이 된다.

각 그룹의 점수와 화면의 가장 위에 보여지는 글자가 순서대로 주어진다. 이 때, 선영이가 테트리스 같은 게임에서 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 정수 B1, B2, B3, B4, B5가 주어진다. i=1,2,3,4인 경우에 Bi는 글자 i개로 이루어진 그룹의 점수이고, B5는 글자 5개 또는 그 이상으로 이루어진 그룹의 점수이다. 이 다섯 정수는 100보다 작거나 같다.

둘째 줄에는 화면에 보여지는 글자의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

셋째 줄에는 화면에 보여지는 글자 N개가 순서대로 주어진다. 글자는 알파벳 대문자이다.

출력

첫째 줄에 선영이가 얻을 수 있는 가장 높은 점수를 출력한다.

예제 입력 1

3 3 10 3 3
17
AAABBCCCAAACBAAAB

예제 출력 1

56

힌트

예제의 경우에 아래와 같이 쌓으면 가장 높은 점수를 얻을 수 있다.

|   | 
|A  | 
|A  | 
|A  | 
|B  | 
|A  | 
|A  | 
|A  | 
|C  | 
|ABC| 
|ABC| 
|ABC| 
+---+
W3sicHJvYmxlbV9pZCI6IjMxNjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQgXHVhYzE5XHVjNzQwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNCBcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMTM4IFx1YzVmNFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVkNjU0XHViYTc0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHViY2Y0XHVjNWVjXHVjOWM0XHViMmU0LiBcdWFlMDBcdWM3OTBcdWFjMDAgXHViY2Y0XHVjNWVjXHVjOWMwXHViYTc0LCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMTM4IFx1YzVmNFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVjNWY0XHVjNzc0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1YzVmNFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViNzk4XHVjNWQwIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWIxOTNcdWFjZTAsIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWM1ZjRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzcwNFx1YzVkMCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViMTkzXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMDljIFx1ZDZjNFx1YzVkMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVjNWJiXHVjNzQwIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWFjMDEgXHVjNWY0XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM1ZjRcdWM3NTggXHVjODEwXHVjMjE4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YjJlOFx1YzViNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZGY4XHViOGY5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWNjM2VcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzViNFx1YjVhNCBcdWM1ZjRcdWM3NTggXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXRsaWtlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0OHB4OyB3aWR0aDoyMDhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHViMjk0IFx1Y2QxZCA0XHVhYzFjXHVjNzU4IFx1YWRmOFx1YjhmOVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM3NTggXHVkMDZjXHVhZTMwKFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOClcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwNmNcdWFlMzBcdWFjMDAgMVx1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NDAgM1x1YzgxMCwgMlx1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NDAgN1x1YzgxMCwgM1x1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NDAgNVx1YzgxMFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgNSszKzUrNz0yMFx1YzgxMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM3NTggXHVjODEwXHVjMjE4XHVjNjQwIFx1ZDY1NFx1YmE3NFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YmNmNFx1YzVlY1x1YzljMFx1YjI5NCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNCBcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZTRcdWMxMmYgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBCPHN1Yj4xPFwvc3ViPiwgQjxzdWI+MjxcL3N1Yj4sIEI8c3ViPjM8XC9zdWI+LCBCPHN1Yj40PFwvc3ViPiwgQjxzdWI+NTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpPTEsMiwzLDRcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIEI8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWUwMFx1Yzc5MCBpXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFkZjhcdWI4ZjlcdWM3NTggXHVjODEwXHVjMjE4XHVjNzc0XHVhY2UwLCBCPHN1Yj41PFwvc3ViPlx1YjI5NCBcdWFlMDBcdWM3OTAgNVx1YWMxYyBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZGY4XHViOGY5XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjJlNFx1YzEyZiBcdWM4MTVcdWMyMThcdWIyOTQgMTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjU0XHViYTc0XHVjNWQwIFx1YmNmNFx1YzVlY1x1YzljMFx1YjI5NCBcdWFlMDBcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWJjZjRcdWM1ZWNcdWM5YzBcdWIyOTQgXHVhZTAwXHVjNzkwIE5cdWFjMWNcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZTAwXHVjNzkwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjMzEzXHVjNzNjXHViYTc0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPnwgICB8IFxyXG58QSAgfCBcclxufEEgIHwgXHJcbnxBICB8IFxyXG58QiAgfCBcclxufEEgIHwgXHJcbnxBICB8IFxyXG58QSAgfCBcclxufEMgIHwgXHJcbnxBQkN8IFxyXG58QUJDfCBcclxufEFCQ3wgXHJcbistLS0rPFwvcHJlPiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImtvY2tpY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBMdWthIGlzIHBsYXlpbmcgYW4gaW50ZXJlc3RpbmcgdGV0cmlzLWxpa2UgZ2FtZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGhlIGJlZ2lubmluZyBvZiB0aGUgZ2FtZSwgdGhlcmUgYXJlIHRocmVlIGVtcHR5IGNvbHVtbnMgb24gdGhlIHNjcmVlbi4gRHVyaW5nIHRoZSBnYW1lLCBsZXR0ZXJzIGFwcGVhciBvbiB0aGUgdG9wIG9mIHRoZSBzY3JlZW4uIFdoZW4gYSBsZXR0ZXIgYXBwZWFycywgTHVrYSBjaG9vc2VzIG9uZSBvZiB0aGUgY29sdW1ucyBhbmQgcHV0cyB0aGlzIGxldHRlciBvbiB0b3Agb2YgdGhlIHRvcG1vc3QgbGV0dGVyIGluIHRoYXQgY29sdW1uLCBvciBvbiB0aGUgYm90dG9tIGlmIHRoYXQgY29sdW1uIGlzIGVtcHR5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGVuIHRoZSBnYW1lIGlzIG92ZXIsIHdlIGRlZmluZSB0aGUgdG90YWwgbnVtYmVyIG9mIHBvaW50cyB0aGF0IEx1a2EgZ2V0cyBhcyBzdW0gb2YgdGhlIHBvaW50cyBmb3IgZWFjaCBjb2x1bW4uIFRoZSBudW1iZXIgb2YgcG9pbnRzIGZvciBhIGNvbHVtbiBpcyBjYWxjdWxhdGVkIGluIHRoZSBmb2xsb3dpbmcgd2F5OiB3ZSBmaXJzdCBmaW5kIGdyb3VwcyBvZiBpZGVudGljYWwgY29uc2VjdXRpdmUgbGV0dGVycyAoYm9yZGVycyBiZXR3ZWVuIHR3byBncm91cHMgYXJlIGJldHdlZW4gZGlmZmVyZW50IGxldHRlcnMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIGxldHRlcnMgaW4gc29tZSBjb2x1bW4gYXJlOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RldGxpa2UucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ4cHg7IHdpZHRoOjIwOHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPnRoZW4gdGhpcyBjb2x1bW4gY29uc2lzdHMgb2YgNCBncm91cHMuIE5vdywgZm9yIGVhY2ggb2YgdGhlIGdyb3Vwcywgd2UgZ2V0IHNvbWUgbnVtYmVyIG9mIHBvaW50cyB0aGF0IGRlcGVuZHMgb25seSBvbiB0aGUgbnVtYmVyIG9mIGxldHRlcnMgaW4gdGhhdCBncm91cC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHdlIGdldCAzIHBvaW50cyBmb3IgdGhlIGdyb3VwcyB3aXRoIHNpemUgMSwgNyBwb2ludHMgZm9yIHRoZSBncm91cHMgd2l0aCBzaXplIDIsIGFuZCA1IHBvaW50cyBmb3IgdGhlIGdyb3VwcyB3aXRoIHNpemUgMywgdGhlbiB0aGUgbnVtYmVyIG9mIHBvaW50cyBmb3IgdGhlIGV4YW1wbGUgY29sdW1uIHdvdWxkIGJlIDUrMys1Kzc9MjAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiBhIHNlcXVlbmNlIG9mIGxldHRlcnMgYW5kIHRoZSBhc3NpZ25tZW50IG9mIHNjb3JlcyB0byBncm91cCBzaXplcywgZmluZHMgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBvaW50cyB0aGF0IEx1a2EgY2FuIGdldCBpbiB0aGlzIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBmaXZlIGludGVnZXJzIEI8c3ViPjE8XC9zdWI+LCBCPHN1Yj4yPFwvc3ViPiwgQjxzdWI+MzxcL3N1Yj4sIEI8c3ViPjQ8XC9zdWI+LCBhbmQgQjxzdWI+NTxcL3N1Yj4uIEZvciBpPTEsMiwzLDQgdGhlIG51bWJlciBCPHN1Yj5pPFwvc3ViPiBpcyB0aGUgbnVtYmVyIG9mIHBvaW50cyBmb3IgZ3JvdXBzIGNvbnNpc3Rpbmcgb2YgaSBsZXR0ZXJzIGFuZCB0aGUgbnVtYmVyIEI8c3ViPjU8XC9zdWI+IGlzIHRoZSBudW1iZXIgb2YgcG9pbnRzIGZvciBncm91cHMgb2YgNSBvciBtb3JlIGxldHRlcnMuIEVhY2ggb2YgdGhlc2UgNSBudW1iZXJzIHdpbGwgYmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyAxMDAwICZuZGFzaDsgdGhlIG51bWJlciBvZiBsZXR0ZXJzIGFwcGVhcmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBOIHVwcGVyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0ICgmIzM5O0EmIzM5Oy0mIzM5O1omIzM5OyksIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IGFwcGVhciBvbiB0aGUgdG9wIG9mIHRoZSBzY3JlZW4gZHVyaW5nIHRoZSBnYW1lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBvaW50cyBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cHJlPlxyXG58ICAgfCBcclxufEEgIHwgXHJcbnxBICB8IFxyXG58QSAgfCBcclxufEIgIHwgXHJcbnxBICB8IFxyXG58QSAgfCBcclxufEEgIHwgXHJcbnxDICB8IFxyXG58QUJDfCBcclxufEFCQ3wgXHJcbnxBQkN8IFxyXG4rLS0tKzxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=