시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwNmNcdWFlMzBcdWFjMDAgMVx1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NDAgM1x1YzgxMCwgMlx1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NDAgN1x1YzgxMCwgM1x1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NDAgNVx1YzgxMFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgNSszKzUrNz0yMFx1YzgxMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM3NTggXHVjODEwXHVjMjE4XHVjNjQwIFx1ZDY1NFx1YmE3NFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YmNmNFx1YzVlY1x1YzljMFx1YjI5NCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVkMTRjXHVkMmI4XHViOWFjXHVjMmE0IFx1YWMxOVx1Yzc0MCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlNFx1YzEyZiBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IEI8c3ViPjE8XC9zdWI+LCBCPHN1Yj4yPFwvc3ViPiwgQjxzdWI+MzxcL3N1Yj4sIEI8c3ViPjQ8XC9zdWI+LCBCPHN1Yj41PFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGk9MSwyLDMsNFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgQjxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVhZTAwXHVjNzkwIGlcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWM4MTBcdWMyMThcdWM3NzRcdWFjZTAsIEI8c3ViPjU8XC9zdWI+XHViMjk0IFx1YWUwMFx1Yzc5MCA1XHVhYzFjIFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFkZjhcdWI4ZjlcdWM3NTggXHVjODEwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzQgXHViMmU0XHVjMTJmIFx1YzgxNVx1YzIxOFx1YjI5NCAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2NTRcdWJhNzRcdWM1ZDAgXHViY2Y0XHVjNWVjXHVjOWMwXHViMjk0IFx1YWUwMFx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjU0XHViYTc0XHVjNWQwIFx1YmNmNFx1YzVlY1x1YzljMFx1YjI5NCBcdWFlMDBcdWM3OTAgTlx1YWMxY1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFlMDBcdWM3OTBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWMzMTNcdWM3M2NcdWJhNzQgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+fCAgIHwgXHJcbnxBICB8IFxyXG58QSAgfCBcclxufEEgIHwgXHJcbnxCICB8IFxyXG58QSAgfCBcclxufEEgIHwgXHJcbnxBICB8IFxyXG58QyAgfCBcclxufEFCQ3wgXHJcbnxBQkN8IFxyXG58QUJDfCBcclxuKy0tLSs8XC9wcmU+Iiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoia29ja2ljZSIsImRlc2NyaXB0aW9uIjoiPHA+TGl0dGxlIEx1a2EgaXMgcGxheWluZyBhbiBpbnRlcmVzdGluZyB0ZXRyaXMtbGlrZSBnYW1lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGUgYmVnaW5uaW5nIG9mIHRoZSBnYW1lLCB0aGVyZSBhcmUgdGhyZWUgZW1wdHkgY29sdW1ucyBvbiB0aGUgc2NyZWVuLiBEdXJpbmcgdGhlIGdhbWUsIGxldHRlcnMgYXBwZWFyIG9uIHRoZSB0b3Agb2YgdGhlIHNjcmVlbi4gV2hlbiBhIGxldHRlciBhcHBlYXJzLCBMdWthIGNob29zZXMgb25lIG9mIHRoZSBjb2x1bW5zIGFuZCBwdXRzIHRoaXMgbGV0dGVyIG9uIHRvcCBvZiB0aGUgdG9wbW9zdCBsZXR0ZXIgaW4gdGhhdCBjb2x1bW4sIG9yIG9uIHRoZSBib3R0b20gaWYgdGhhdCBjb2x1bW4gaXMgZW1wdHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoZW4gdGhlIGdhbWUgaXMgb3Zlciwgd2UgZGVmaW5lIHRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIHRoYXQgTHVrYSBnZXRzIGFzIHN1bSBvZiB0aGUgcG9pbnRzIGZvciBlYWNoIGNvbHVtbi4gVGhlIG51bWJlciBvZiBwb2ludHMgZm9yIGEgY29sdW1uIGlzIGNhbGN1bGF0ZWQgaW4gdGhlIGZvbGxvd2luZyB3YXk6IHdlIGZpcnN0IGZpbmQgZ3JvdXBzIG9mIGlkZW50aWNhbCBjb25zZWN1dGl2ZSBsZXR0ZXJzIChib3JkZXJzIGJldHdlZW4gdHdvIGdyb3VwcyBhcmUgYmV0d2VlbiBkaWZmZXJlbnQgbGV0dGVycykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgbGV0dGVycyBpbiBzb21lIGNvbHVtbiBhcmU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGV0bGlrZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDhweDsgd2lkdGg6MjA4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+dGhlbiB0aGlzIGNvbHVtbiBjb25zaXN0cyBvZiA0IGdyb3Vwcy4gTm93LCBmb3IgZWFjaCBvZiB0aGUgZ3JvdXBzLCB3ZSBnZXQgc29tZSBudW1iZXIgb2YgcG9pbnRzIHRoYXQgZGVwZW5kcyBvbmx5IG9uIHRoZSBudW1iZXIgb2YgbGV0dGVycyBpbiB0aGF0IGdyb3VwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgd2UgZ2V0IDMgcG9pbnRzIGZvciB0aGUgZ3JvdXBzIHdpdGggc2l6ZSAxLCA3IHBvaW50cyBmb3IgdGhlIGdyb3VwcyB3aXRoIHNpemUgMiwgYW5kIDUgcG9pbnRzIGZvciB0aGUgZ3JvdXBzIHdpdGggc2l6ZSAzLCB0aGVuIHRoZSBudW1iZXIgb2YgcG9pbnRzIGZvciB0aGUgZXhhbXBsZSBjb2x1bW4gd291bGQgYmUgNSszKzUrNz0yMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGEgc2VxdWVuY2Ugb2YgbGV0dGVycyBhbmQgdGhlIGFzc2lnbm1lbnQgb2Ygc2NvcmVzIHRvIGdyb3VwIHNpemVzLCBmaW5kcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcG9pbnRzIHRoYXQgTHVrYSBjYW4gZ2V0IGluIHRoaXMgZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGZpdmUgaW50ZWdlcnMgQjxzdWI+MTxcL3N1Yj4sIEI8c3ViPjI8XC9zdWI+LCBCPHN1Yj4zPFwvc3ViPiwgQjxzdWI+NDxcL3N1Yj4sIGFuZCBCPHN1Yj41PFwvc3ViPi4gRm9yIGk9MSwyLDMsNCB0aGUgbnVtYmVyIEI8c3ViPmk8XC9zdWI+IGlzIHRoZSBudW1iZXIgb2YgcG9pbnRzIGZvciBncm91cHMgY29uc2lzdGluZyBvZiBpIGxldHRlcnMgYW5kIHRoZSBudW1iZXIgQjxzdWI+NTxcL3N1Yj4gaXMgdGhlIG51bWJlciBvZiBwb2ludHMgZm9yIGdyb3VwcyBvZiA1IG9yIG1vcmUgbGV0dGVycy4gRWFjaCBvZiB0aGVzZSA1IG51bWJlcnMgd2lsbCBiZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDEwMDAgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIGxldHRlcnMgYXBwZWFyaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIE4gdXBwZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQgKCYjMzk7QSYjMzk7LSYjMzk7WiYjMzk7KSwgaW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgYXBwZWFyIG9uIHRoZSB0b3Agb2YgdGhlIHNjcmVlbiBkdXJpbmcgdGhlIGdhbWUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJm5kYXNoOyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcG9pbnRzIGZyb20gdGhlIHRhc2sgZGVzY3JpcHRpb24uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwcmU+XHJcbnwgICB8IFxyXG58QSAgfCBcclxufEEgIHwgXHJcbnxBICB8IFxyXG58QiAgfCBcclxufEEgIHwgXHJcbnxBICB8IFxyXG58QSAgfCBcclxufEMgIHwgXHJcbnxBQkN8IFxyXG58QUJDfCBcclxufEFCQ3wgXHJcbistLS0rPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==