CLAW - Captain Claw

Captain Claw is at the bank of a river of acid and he needs to cross it. The river is x metres wide but Captain Claw can jump at most d metres.

However, the Captain can jump on stones which keep appearing in the stream.

Captain Claw River of Acid

Input

There are multiple test cases. For each test case.

The first line contains n, x and d.

The next n lines denotes subsequent seconds.

For each line, the first integer, c, denotes the number of number of stones appearing in this second.

Then c integers follow.

The ith integer means that a stone would appears at the position of that integer.

Find the minimum time needed by the Captain to cross the river.

1 <= t <= 30

1 <= x <= 10^5

1 <= d <= x

1 <= n <= 10^3

1 <= sum(c) <= 10^5

Assumption

Captain Claw is super fast. The time taken by jumps is negligible to a second.

Output

Print a single integer in each line - the time taken to cross the river.

Output -1 if its not possible to cross the river in n seconds.

Example

Input:
1
4 6 2
1 5
1 3
1 1
1 2

Output:
3

Explanation:

Sec 1: Captain Waits

Sec 2: Captain Waits

Sec 3: Captain Jumps from bank(0) → 1 → 3 → 5 → bank(6)


Added by:sarfaraz
Date:2016-01-20
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2023-10-20 05:22:28
I don’t understand why I don’t have a solution, can you tell me, my shipment number is 32051024?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.