Opening The Ballot Box

All submissions for this problem are available.
Problem Description
Now that the votes have been casted, its time to count them. The ballot box has been locked with a secret code and has been handled to the Election Commission for
counting. The ballot box is very secure. It has 5 digits on its lock and only a particular combination of the digits can unlock it. The digits on the lock can be
changed only with the help of a laser machine.
The laser machine is very unique. It has K keys (with a number on each key) on it. In each step, it
multiplies the 5 digit number on the ballot box with any of its keys and then takes the remainder with 10^{5} so as to make the number back to 5 digits. Note
that numbers are have leading 0's in case it is less than 5 digits. But using the laser machine is very expensive. Each step costs C Rupees. So the election
commission wants to know the minimum cost to unlock the ballot box.
Given the initial code, the final code (which unlocks the box), the K Keys and the cost per operation C, your job is to help find the minimum cost to
unlock the box, or report that the box cannot be opened.
Input
The first line of the input consists of the number of cases (T). T test cases follows. Each test case begins with a line containing 4 numbers K C I F
,
where K is the number of Keys on the laser, C is the cost of using laser once, I is a 5 digit initial code and F is a 5 digit final code to unlock. Next line contains
K numbers, keys[] which are the keys on the laser machine.
Output
For each test case, output a line with one number which is the minimum cost to open the box. If the box can never be opened output 1 instead.
Constraints
T ≤ 50
1 ≤ K ≤ 10
1 ≤ C ≤ 10^{7}
I, F are 5 digit numbers and can have leading zero's. 0 ≤ Keys[] ≤ 10^{5}
Sample Cases
2 2 10 00002 00016 2 4 2 10 00002 00001 2 4
Output
20 1
Explanations
 In the first case, you can use the key with number 2 to first reach to 4 and then use key 4 to reach 16. So laser was used two times.
 In the second case, whatever you multiply, you will never be able to reach an odd number.
Author:  phantom11 
Tags  phantom11 
Date Added:  12022014 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, GO, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 