## ALIEN3 - Aliens at the subway

no tags

The female Alien moved to the biggest city in the world, this city has a giant subway system, this subway is always full of people, the Alien doesn't want to see humans and she wants to stay the least time possible in the subway system.

Preventing this scenario, the Alien brought from her planet some interesting and very rare objects, she calls this objects “Portable Teleporters”, with these objects the alien is on the capacity to teleport and ignore the next K stations, as you may know, this objects are limited and it can be used once.

As the city is so big that the subway is always full, she wants to stay the least number stations as possible, the Alien will start from station 0, wishing to go up to an station L, the subway is formed by N+1 (0 through N) stations and the Alien has K “Portable Teleporters”.

When the Alien uses a “Portable Teleporters” she will be teleported immediately to the I+Kj station, being I the station the alien was on and Kj the value of the Portable Teleporter.

If she is unable to use a teleporter or is better for her to go into the next station using the subway, she can do it, however, she can only move forward, NEVER backwards, furthermore, the Alien may not leave the limits of the stations (that means she can't go to any station before station 0 or any station after station N).

As you may know, the Alien doesn't wants to see a large number of people, to prevent this, she wants to visit as maximum T stations, if she can't reach her destination on T stations, she will simply exit the subway and will start walking on the city.

Your task is simple, given the N stations, the K objects and their values and the station the Alien wants to go, the L station the alien wants to go and the T number of tries, output the least stations visited so she can reach her destination.

INPUT:

The Input will start with an integer P denoting the test cases, then P cases will follow, each case have three lines, the first line contains two integers N and K, denoting the N stations and the K portable teleporters, next line will contain K integers, denoting the value of each teleporter, the last line for each case will contain two integers L and T, that it will be the last station the alien wants to go and the T number of stations she wants to visit as maximum.

OUTPUT:

The output will consists on P lines, each line containing the string "Scenario #i: " where i is the test case you're analyzing (starting by 1), followed by the minimum stations visited by the Alien to reach her destination, if she can't reach her destination on maximum T stations, print -1.

 INPUT OUTPUT 4 12 6 1 3 4 1 2 -2 10 10 12 6 1 3 2 1 2 -2 10 10 10 2 6 -2 5 10 10 2 1 1 10 5 Scenario #1: 4Scenario #2: 6Scenario #3: 3Scenario #4: -1

"Blank line between input sample data is just for clarification and understanding of the problem"

Explanation of the first test case:

She teleports from station 0 to station 4 using the third teleporter, from 4 to 7 using the second teleporter, from 7 to 9 using the fifth teleporter and she can either walk to the next station or use another teleporter.

Explanation of the last case:

She can't reach the station 10 going through only 5 stations, the answer should be then -1.

CONSTRAINTS:

1 <= P <= 50

1 <= N <= 100

1 <= K <= 17

-100 <= Ki <= 100

0 <= L <= N

1 <= T <= 50