타일링 테라스

탈리아는 자카르타 외곽의 버려진 집을 막 샀다. 이 집에는 길고 넓은 마당이 있으며, 이 마당은 $1 \times N$ 칸으로 이루어진 일차원 격자로 나타낼 수 있다. 집을 꾸미려고 탈리아는 마당의 칸을 타일로 덮어 테라스를 만들 계획이다. 각 칸은 흙(.) 또는 바위(#)이며, 바위 칸은 최대 50개이다.

귀신을 무서워하는 탈리아는 귀신을 쫓는 신비한 타일을 쓰려고 한다. 타일은 세 종류가 있다.

• 1형: $1 \times 1$ 칸을 덮으며, 흙 칸(.)에만 놓을 수 있다.
• 2형: $1 \times 2$ 칸을 덮으며, 연속한 흙 두 칸(..)에만 놓을 수 있다.
• 3형: $1 \times 3$ 칸을 덮으며, 흙-바위-흙이 연속한 칸(.#.)에만 놓을 수 있다.

1형, 2형, 3형 타일은 하루에 각각 $G_1$, $G_2$, $G_3$ 마리의 귀신을 쫓는다. 다음 규칙을 지켜야 한다.

• 타일끼리 겹치면 안 된다. 각 칸은 최대 한 개의 타일로 덮인다.
• 1형 타일은 최대 $K$개까지 쓸 수 있다. 2형과 3형 타일은 개수 제한이 없다.

탈리아는 테라스가 쫓는 귀신의 수를 최대로 만들고자 한다. 쫓는 귀신의 수가 최대이기만 하면 모든 칸을 덮을 필요는 없다. 하루에 쫓을 수 있는 귀신 수의 최댓값을 구하라.

첫 줄에 다섯 정수 $N$, $K$, $G_1$, $G_2$, $G_3$ ($1 \le N \le 100000$, $0 \le K \le N$, $0 \le G_1, G_2, G_3 \le 1000$)이 주어진다. 각각 칸의 수, 1형 타일의 최대 개수, 1형·2형·3형 타일 한 개가 하루에 쫓는 귀신의 수이다. 다음 줄에는 길이 $N$의 문자열이 주어지며, 각 문자는 흙(.) 또는 바위(#)이다. 바위 칸은 최대 50개이다.

하루에 쫓을 수 있는 귀신 수의 최댓값을 정수 하나로 출력한다.