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.

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⁵

1 ≤ d ≤ x

1 ≤ n ≤ 10³

1 ≤ sum(c) ≤ 10⁵

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)