Nam đang có ý định đi du lịch qua 3 nước là X, Y, Z. 3 đất nước này có một đặc điểm chung là đều có n thành phố (các thành phố được đánh số từ 1 tới n). 

Chi phí để đi mua vé di chuyển từ nước này sang nước khác là d đồng

Mỗi đất nước lại được chia ra 3 loại tỉnh về mức độ thu nhập(các tỉnh loại 0,  các tỉnh loại 1, và các tỉnh loại 2), và chi phí để thăm quan tỉnh thuộc từng loại đó là a đồng, b đồng, c đồng tương ứng. Chi phí để đi du lịch từ tỉnh này đến tỉnh khác trong một đất nước coi như bằng 0.

Mục đích của Nam là đi tới thành phố cuối cùng của đất nước Y với chi phí thấp nhất

Lúc đầu, Nam bắt đầu từ thành phố đầu tiên của bất kỳ đất nước nào.

Nhưng có một số giới hạn dành cho Nam:

giới hạn 1. Khi Nam muốn di chuyển sang đất nước tiếp theo, thì Nam phải di chuyển sang tỉnh có cùng chỉ số với đất nước trước

giới hạn 2. Từ đất nước X, bạn chỉ có thể di chuyển sang đất nước Y, và từ Z, bạn chỉ có thể di chuyển sang đất nước Y, và từ đất nước Y, bạn có thể tới bất kỳ nước nào khác

giới hạn 3. Bạn có thể đi qua giữa các đất nước đúng k lần

Giới hạn

1<=n<=100000

0<=k<=10

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

0, 1, 2  biểu thị cho các tỉnh loại 0, loại 1 và loại 2

Input

Dòng đầu tiên gồm các số n,k,a,b,c,d, số các thành phố trong mỗi đất nước, số lần được phép đi qua các đất nước, chi phí để thăm quan thành phố loại 0, chi phí để thăm quan thành phố loại 1, và chi phí để thăm quan thành phố loại 2, và chi phí để đi du lịch từ đất nước này sang đất nước khác

3 dòng sau đó, mỗi dòng là một xâu có chiều dài n, gồm một trong các số 0,1,2, trong đó 0,1,2, biểu thị loại thành phố, các thành phố được đánh số từ 1 đến n

Ouput

Đưa ra một số nguyên, biểu thị câu trả lời cho mỗi câu hỏi