시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 632 185 151 31.656%

문제

오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다. (즉, 오른쪽 버튼 같은 것은 없다)

입력

첫째 줄에 p와 w가 주어진다. (1<=p,w<=1,000) p는 버튼을 한번 누르는데 걸리는 시간이고, w는 AC와 같은, 같은 숫자인 문자를 연속으로 찍기 위해 기다리는 시간을 의미한다. 그리고 둘째 줄에는 적을 문자열이 주어진다. 단, 이 문자열의 길이는 1000보다 작고, 맨 앞에 공백이 들어오는 경우는 없다고 가정하여도 좋다. 문자열은 알파벳 대문자와 띄어쓰기만으로 이루어져 있다.

출력

첫째 줄에 메시지를 적는데 걸리는 시간을 출력한다.

예제 입력 1

2 10
ABBAS SALAM

예제 출력 1

72
W3sicHJvYmxlbV9pZCI6IjIwMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWJhNTRcdWMyZGNcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDU3OFx1YjRkY1x1ZDNmMCBcdWM3OTBcdWQzMTBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjNzkwXHVkMzEwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWM1YjRcdWI1YTQgXHVjNjAxXHVjNWI0IFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWNlNThcdWI4MjRcdWFjZTAgXHVkNTYwIFx1YjU0YywgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCwgMVx1YmM4OFx1Yzc0MCBcdWIyMDRcdWI5N2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWNjMGRcdWQ3OGNcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViOWNjXHVjNTdkXHVjNWQwIEFDXHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWNlNThcdWI4MjQgXHVkNTVjXHViMmU0XHViYTc0IEFcdWI5N2MgXHVjZTU4XHVhY2UwIFx1YjA5YyBcdWQ2YzQgXHVjNzdjXHVjODE1IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFlMzBcdWIyZTRcdWI5YjAgXHVkNmM0IENcdWI5N2MgXHVjZTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gKFx1Yzk4OSwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmM4NFx1ZDJiYyBcdWFjMTlcdWM3NDAgXHVhYzgzXHVjNzQwIFx1YzVjNlx1YjJlNCk8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvc21zLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3NHB4OyB3aWR0aDoxMzdweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBwXHVjNjQwIHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsdDs9cCx3Jmx0Oz0xLDAwMCkgcFx1YjI5NCBcdWJjODRcdWQyYmNcdWM3NDQgXHVkNTVjXHViYzg4IFx1YjIwNFx1Yjk3NFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0XHVhY2UwLCB3XHViMjk0IEFDXHVjNjQwIFx1YWMxOVx1Yzc0MCwgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yzc3OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjNWYwXHVjMThkXHVjNzNjXHViODVjIFx1Y2MwZFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZTMwXHViMmU0XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgwMVx1Yzc0NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTgsIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhY2UwLCBcdWI5ZTggXHVjNTVlXHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM1ZWNcdWIzYzQgXHVjODhiXHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWI3NDRcdWM1YjRcdWM0ZjBcdWFlMzBcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM4MDFcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlc3QgU01TIHRvIFR5cGUiLCJkZXNjcmlwdGlvbiI6IjxwPlVzaW5nIFNNUyB0b2RheSBpcyBtb3JlIHRoYW4gYSBwbGVhc2luZyBob2JieS4gQXMgdGhlIG51bWJlciBvZiBtZXNzYWdlcyBvbmUgc2VuZHMgdGhyb3VnaCB0aGlzIHNlcnZpY2UgZ3Jvd3MsIHRoZSBuZWVkIHRvIHR5cGUgdGhlbSBmYXN0IGlzIGJldHRlciBmZWx0LiBTb21ldGltZXMsIG9uZSB3b25kZXJzIGhvdyBmYXN0IGEgbWVzc2FnZSBjYW4gYmUgdHlwZWQuIENoYW5naW5nIHNvbWUgd29yZHMgdG8gdGhlaXIgc3lub255bXMsIG1pZ2h0IGhlbHAgdHlwZSB0aGUgd2hvbGUgbWVzc2FnZSBmYXN0ZXIsIGlmIHdlIHdlcmUgYWJsZSB0byBxdWlja2x5IGNhbGN1bGF0ZSB0aGUgdGltZSBuZWVkZWQgZm9yIGEgc3BlY2lmaWMgbWVzc2FnZS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGZvbGxvd2luZywgd2UgYXNzdW1lIHRoYXQgZWFjaCBtZXNzYWdlIGlzIGEgc3RyaW5nIG9mIGNhcGl0YWwgRW5nbGlzaCBsZXR0ZXJzIGFuZCBzcGFjZSBjaGFyYWN0ZXIuIFRoZSBsZXR0ZXJzICYjMzk7QSYjMzk7IHRocm91Z2ggJiMzOTtaJiMzOTsgYXJlIGFzc2lnbmVkIHRvIGtleXMgJiMzOTsyJiMzOTsgdG8gJiMzOTs5JiMzOTssIGFzIGluIHRoZSBmb2xsb3dpbmcgZmlndXJlLiBUbyB0eXBlIGEgbGV0dGVyLCBvbmUgc2hvdWxkIHByZXNzIGl0cyBrZXkgMSwgMiwgMywgb3IgNCB0aW1lcywgZGVwZW5kaW5nIG9uIHRoZSBwb3NpdGlvbiBvZiB0aGUgbGV0dGVyIGZyb20gbGVmdCB0byByaWdodC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvc21zLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxNzRweDsgd2lkdGg6MTM3cHhcIiBcLz5JZiB0d28gY29uc2VjdXRpdmUgbGV0dGVycyBvZiB0aGUgbWVzc2FnZSBhcmUgbWFwcGVkIHRvIG9uZSBrZXksIG9uZSBzaG91bGQgd2FpdCBmb3IgdGhlIGZpcnN0IGxldHRlciB0byBiZSBmaXhlZCBvbiB0aGUgc2NyZWVuIGFuZCB0aGVuIHVzZSB0aGUga2V5IGFnYWluIHRvIHR5cGUgdGhlIHNlY29uZCBvbmUuIEZvciBpbnN0YW5jZSwgdG8gdHlwZSB0aGUgbGV0dGVyICYjMzk7WCYjMzk7LCBvbmUgc2hvdWxkIHByZXNzICYjMzk7OSYjMzk7IHR3aWNlLiBJZiB0aGUgbmV4dCBsZXR0ZXIgb2YgdGhlIG1lc3NhZ2UgaXMgbm90IG9uIHRoZSBzYW1lIGtleSwgb25lIGNhbiBjb250aW51ZSB0byB0eXBlIHRoZSByZXN0IG9mIHRoZSBtZXNzYWdlLiBPdGhlcndpc2UsIG9uZSBoYXMgdG8gd2FpdCBmb3Igc29tZSB0aW1lLCBzbyB0aGF0IHRoZSB0eXBlZCAmIzM5O1gmIzM5OyBpcyBmaXhlZCwgYW5kIHRoZW4gdGhlIG5leHQgbGV0dGVyICgmIzM5O1cmIzM5OywgJiMzOTtYJiMzOTssICYjMzk7WSYjMzk7LCBvciAmIzM5O1omIzM5OykgY2FuIGJlIHR5cGVkLiBUbyB0eXBlIHdoaXRlc3BhY2UsIHdlIHVzZSB0aGUga2V5ICYjMzk7MSYjMzk7LiBBcyB0aGVyZSBpcyBubyBsZXR0ZXIgbWFwcGVkIHRvIHRoZSBrZXkgJiMzOTsxJiMzOTssIHRoZSB3aGl0ZXNwYWNlIG5lZWRzIG5vIHRpbWUgdG8gYmUgZml4ZWQuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIHRpbWUgbmVlZGVkIHRvIHByZXNzIGFueSBrZXksIGFuZCB0aGUgdGltZSBvbmUgc2hvdWxkIHdhaXQgZm9yIGEgbGV0dGVyIHRvIGJlIGZpeGVkLiBZb3VyIHByb2dyYW0gc2hvdWxkIGZpbmQgdGhlIG1pbmltdW0gdGltZSBuZWVkZWQgdG8gdHlwZSBhIG5vbmVtcHR5IHN0cmluZywgZ2l2ZW4gdGhlIGFib3ZlIHJ1bGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29udGFpbnMgbXVsdGlwbGUgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LCBjb250YWlucyB0ICwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRoYXQgZm9sbG93LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgdCBibG9ja3MsIGRlc2NyaWJlcyBhIHRlc3QgY2FzZS4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBibG9jayBjb250YWlucyBwIGFuZCB3ICgxICZsZTsgcCwgdyAmbGU7IDEwMDApICwgd2hpY2ggc2hvdyB0aGUgYW1vdW50IG9mIHRpbWUgaW4gbWlsbGlzZWNvbmRzIGZvciBwcmVzc2luZyBhIGxldHRlciBhbmQgd2FpdGluZyBmb3IgaXQgdG8gYmUgZml4ZWQsIHJlc3BlY3RpdmVseS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgbm9uLWVtcHR5IHN0cmluZyBvZiBsZW5ndGggYXQgbW9zdCAxMDAwLCBjb25zaXN0aW5nIG9mIHNwYWNlcyBvciBjYXBpdGFsIEVuZ2xpc2ggbGV0dGVycy4gVGhlcmUgaXMgbm8gbGVhZGluZyBvciB0cmFpbGluZyBzcGFjZXMgaW4gYSBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIHNob3dpbmcgdGhlIHRpbWUgbmVlZGVkIHRvIHR5cGUgdGhlIG1lc3NhZ2UgaW4gbWlsbGlzZWNvbmRzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=