ALIEN3 - Aliens at the subway

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.

Sample

Input:
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

Output:
Scenario #1: 4
Scenario #2: 6
Scenario #3: 3
Scenario #4: -1

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


Added by:david_8k
Date:2012-06-28
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2017-07-23 21:18:42
Similar to http://www.spoj.com/problems/RIOI_2_3/.
Dfs+Bitmasking. Though the complexity of my code is O((2^k)*n*p), still it got AC.

Last edit: 2017-07-24 16:10:01
2017-04-15 21:28:56 Vipul Srivastava
.

Last edit: 2017-04-15 21:39:47
2017-03-23 07:19:02
AC in one go!
Good bfs+bitmask question!
2014-09-29 19:23:11 dunnohyet
getting wa!! any trickey cases??
2014-09-24 05:39:27 kojak_
AC on first try xD
I DP'ed it. Is there a greedy solution?
2013-01-05 00:47:30 Rocker3011
Take care about the limits, it is from 0 to N. Many many W.A because of this
2012-07-06 05:58:54 Vimal Raj Sharma
Completely lost :(, problem setter is everything ok with input ? I am getting right answer for every input I am trying, but still WA, please check my submission #7267501 I can't find why it is giving WA.
2012-07-06 01:38:04 david_8k
@Mehmet:
For answer 1.
"(...)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)."

For your answer 2. Yes, she can travel to the next station as many times as she wants while she doesn't exceed the limit given.
2012-07-05 17:54:00 mehmetin
Two questions,

1. Are we supposed to assume that there are stations numbered less than 0 or greater than N, which can all be used?

2. Can the alien walk to the next subway more than once in her journey?

Last edit: 2012-07-05 17:55:21
2012-07-04 19:19:00 Vimal Raj Sharma
what will be the output for this

3 1
-1
3 4

3 or -1 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.