양털 염색

청린은 양떼 목장에 새로 취임한 관리인이다. 양떼 목장에는 $N$마리의 양이 살고 있고, 청린은 이제 양들의 양털을 새로 염색해야 한다.

양 한 마리의 양털은 앞에서부터 차례대로 $S$개의 영역으로 이루어져 있으며, 각 영역은 세 가지 색상 중 하나를 가진다. 청린은 이 색상들을 각각 A, B, C라고 부르기로 했다. 특정 색상의 스프레이 한 통을 사용하면 양털의 영역 하나를 해당 색상으로 바꿀 수 있다.

청린의 목장 근처에는 양을 기르는 다른 목장들이 많다. 그래서 청린은 혹시 양이 목장에서 탈출하더라도 자신의 목장의 양이라는 것을 쉽게 알아볼 수 있도록 염색하려고 한다. 청린의 목표를 구체적으로 설명하자면 다음과 같다.

염색이 끝난 뒤, 모든 양의 양털 색을 앞에서부터 살펴보았을 때 처음 $L$개의 영역의 색이 모두 같다고 하자. 청린은 가능한 한 $L$의 최댓값을 크게 만들고 싶다. $(0 \leq L \leq S)$

예를 들어, 세 마리 양의 양털 색이 각각 "ABBCA", "ABBCB", "ABACC"라면, 앞에서부터 두 영역의 색은 모두 같고 세 번째 영역부터는 다른 양이 존재하므로 $L$의 최댓값은 $2$이다.

청린은 스프레이 구매에 사용할 수 있는 자금 $M$원을 가지고 있고, 상술한 목표를 달성하되 가능하다면 자금을 적게 사용하고 싶다. 다행히 청린은 스프레이를 파는 가게의 주인과 친분이 있어서, 같은 색상의 스프레이 $10$개를 묶어서 사면 할인을 받을 수 있다.

총 구매 금액이 $M$원을 넘지 않도록 하면서 만들 수 있는 $L$의 최댓값을 구하고, 그때 사용해야 하는 자금의 최솟값도 함께 구해보자! 단, 구매한 스프레이를 모두 사용할 필요는 없다.

첫 번째 줄에 양의 수 $N$, 사용할 수 있는 자금 $M$, 양 한 마리의 양털을 이루는 영역의 수 $S$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 1\ 000;\ 1 \leq M \leq 10^9;\ 1 \leq S \leq 1\,000)$

두 번째 줄에 색상 A, B, C 스프레이 한 통의 가격이 공백으로 구분되어 주어진다. 각 가격은 $1$ 이상 $10^9$ 이하의 정수이다.

세 번째 줄에 색상 A, B, C 스프레이를 각각 $10$개 묶음으로 구매할 때 할인으로 차감 되는 액수가 공백으로 구분되어 주어진다. 각 액수는 $1$ 이상 $10^9$ 이하의 정수이며, 해당 색상 스프레이 $10$개의 정가보다 작다.

네 번째 줄부터 $N$개의 줄에 걸쳐 각 양의 현재 양털 색 상태를 나타내는 길이 $S$의 문자열이 한 줄에 하나씩 주어진다.

각 문자열은 문자 A, B, C로만 이루어져 있다.

첫 번째 줄에 가능한 $L$의 최댓값과 사용해야 하는 자금의 최솟값을 공백으로 구분하여 출력한다.