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

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

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)