은지는 방을 예쁘게 꾸미기 위해 벽에 띠 모양의 벽지를 만들어 붙이려고 한다.

띠는 N개의 칸으로 구분이 되어 있고 각각의 칸에는 빨강(R), 노랑(Y), 파랑(B) 세 가지 색으로 채우려고 한다. 띠의 특정한 부분에는 미리 색을 지정해서 그 색으로만 채우도록 하고 나머지에는 아무 색으로 채워도 상관이 없다.

일일이 색을 채우기 어려워서 스탬프 한개를 제작해서 앞에서부터 채워나가려고 한다. 스탬프를 제작하기 위해서는 띠의 크기에 따라 비용이 발생하고 스탬프를 한번 찍을 때 마다 스탬프 비용이 발생한다.

예를 들어 스탬프 띠 한칸의 제작비용이 12, 스탬프를 한번 찍는 비용이 7이라고 하고 아래와 같이 길이가 7인 띠를 채우려고 할 때의 비용을 계산해 보자. R***B*Y R과 B, Y는 채워야하는 색을 나타내고 *은 아무 색으로 채워도 된다는 의미이다.

스탬프의 길이가 1인 것으로 채운다면 스탬프 제작비용이 12 * 1 = 12, 스탬프를 7번 찍어야 하므로 비용은 7 * 7 = 49이고 모두 61의 비용이 든다.

스탬프 길이가 2인 것으로 채운다면 스탬프 제작비용이 12 * 2 = 24, 스탬프를 아래와 같이 4번 찍어야 하므로 비용은 7 * 4 = 28이고 모두 52의 비용이 든다.

스탬프 길이가 3 이상인 것으로는 찍을 수 있는 방법이 없으므로 최소비용은 52가 된다.

비용과 띠의 정보를 입력받아 띠를 모두 칠하기 위한 최소비용을 출력하는 프로그램을 작성하시오.

스탬프 timer 1s memory 64MB

스탬프 1s 64MB