In a parallel universe, there are 3 dimensions and each dimension has n cities in it (numbered from 1 to n). People can travel from one dimension to another and that costs them d rubles. Now each dimension has 3 types of cities (0,1,2) in it and the cost of visiting each of them are a,b and c rubles respectively. The travelling cost between cities of the same dimensions can be considered zero.Your goal is to reach the last city of dimension 2 in minimum cost possible. Initially, you are free to start from city 1 of any dimension. But, there are some restrictions given as :

1. When you change dimensions, you remain in the same city as you were on in the previous dimension.

2. From dimension 1, you can only move to dimension 2 and from dimension 3, you can only move to dimension 2, and from dimension 2, you can move to any of the dimensions.

3. You can switch dimensions only k times.

Constraints :

1 <= n <= 100,000

0 <= k <= 10

0 <= a <= b <= c <= d <= 10

Each character denoting the city type is either 0,1 or 2.

Input format:

First line contains n,k,a,b,c,d the number of cities, the number of times dimensions can be switched,cost of visiting city type 0,cost of visiting city type 1,cost of visiting city type 2 and the cost of switching dimensions respectively.

Three lines follow each containing a string of length n containing 0,1 and 2 where 0,1 and 2 denotes the city types.

Output format:

Output a single integer, denoting the answer to the question.