Original statement

Rainbowland is a planet full of life and adorable beings, however, this night, the spies Andreina, Marge and Teresa agreed to breakdown the security of a building led by a teddy bear, this teddy bear is mean! Don't get the wrong idea, the rainbowland spies agency (RSA) just want to make things go right in they colorful and lovable world.

Andreina offered a plan to take control of the building, she and Teresa will go to the roof of another building, seeing the target building, they will tell Marge to take down N rivals on a building of F floors, as she won't use the stairs, there are a series of E elevators that are in the building, the elevator can only go up or down P floors (more explanation on input details).

While Andreina and Teresa sees from outside, Marge must take down immediately the rivals, so they cannot leave them alive, otherwise, they will alert the others and the mission will be failed, when fighting a rival, the rival loses K points of life during each second using normal abilities, you can always assume that Marge won't fail at any fight, in addition, Marge can use some special abilities, these abilities allow Marge to deliver powerful blows, however, these special abilities can only be used once, so she must use it wisely, as Marge doesn't want to waste energy on a single enemy, she will give two special ability punches at most, if she can do it. She can always combine, so at last, she will choose between what is best (If normal attacking, if using one special ability or two and normal attacking).

Help the spies Andreina, Teresa and Marge to find the minimum time so they can take the building and defeat all the rivals, having in consideration that:

1. Marge takes one minute to use the elevator.

2. Each round of fight lasts one minute.

3. Marge starts from floor 1 and she can go from floor 1 to F, never lower nor higher.

4. If Marge uses an special ability or two special abilities, it will still count as she uses on one round (see point 2).

5. There will be from 1 to 7 rivals in all the building.

6. The floor 1 will be always rival free, therefore, the floor 1 will have a value of zero (0).

 

INPUT DETAILS:

First line will contain an integer T denoting T description of the test cases.

For each T you will have four integers F, N, K, E denoting, respectively, the number of floors in the building, the number of special ability that Marge can use, the damage K that Marge delivers after a single blow and the number E of elevators.

Then, in the next line, F integers separated by a single space will follow, denoting the description of the building, a number 0 means that there are no rivals at the floor, a positive number will represent the life points that the rival has at the moment of the assault.

The next line will contain N integers separated by a single space representing the values of a special blow given by Marge, remember that she can only deliver two blows at most for each rivals and she can use only once the special blow.

The next line will contain E integers separated by a single space, meaning the description of the elevators, for each positive number means that the elevator will go up P floors, if the number is negative, means that the elevator will go down P floors, you can always asume that P will never be 0.

 

OUTPUT DETAILS:

For each test case, print the string “Scenario #i: V“ where i denotes the i-th test case you're analyzing (starting from 1) and V is the minimum time that the team can defeat the all rivals, print -1 if the mission will fail.

 

 

 

INPUT	OUTPUT
3 4 2 3 2 0 10 0 15 10 5 2 -1 10 4 2 5 0 0 0 10 0 8 7 8 10 100 10 10 10 80 2 -1 5 -3 1 3 3 2 1 0 100 100 150 200 150 2	Scenario #1: 8 Scenario #2: 26 Scenario #3: -1

 

Explanation of the first test case:

At time 1, Marge goes from floor 1 to floor 3, then, from floor 3 to floor 2, she choose to beat the rival with life 10 with normal blows (it will take 4 units of time to beat it), at this time Marge has already wasted 6 minutes of time, then, she will take the elevator up to floor 4, then will use her two special abilities to deliver a powerful blow on rival at floor 4 with 15 life points (15-10-5 = 0) beating it. Final time of the mission, 8.

 

CONSTRAINTS:

 

1<=T<=10

2<=F<=128

1<=N<=7

1<=K<=1000

1<=E<=50

0<=Fi<=1000

1<=Ni<=1000

-F<=Ei<=F with Ei != 0

 

Clarification: There is no blank lines between Scenarios in the output.