K. Killer Cows
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Farmer John has $$$n$$$ cows that he needs to ferry across a river. He has a boat which can take at most $$$k$$$ cows across at a time. Farmer John will repeatedly ride the boat across the river with some (potentially empty) set of cows until all cows are on the other side of the river.

There are $$$m$$$ sets of cows that cannot be left alone, otherwise they will plan the violent seizure of the farm from their human master. Specifically, for each of these subsets of cows, whenever FJ is riding the boat, they cannot all be on the same side of the river (even if they are with other cows).

Find the minimum number of times FJ needs to ride the boat to ferry all cows across the river, or report that it is impossible.

Input

The first line contains $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq k \leq n \leq 20$$$, $$$0 \leq m \leq 10^5$$$).

The next $$$m$$$ lines each contain a string of length $$$n$$$, consisting of 0s and 1s, representing a subset of cows. The $$$i$$$-th cow is in a subset if and only if the $$$i$$$-th character of that string is a 1.

It is guaranteed that all $$$m$$$ subsets are distinct.

It is also guaranteed that all subsets are nonempty, and no subset is the entire set of cows.

Output

If it is impossible to ferry all the cows to the other side of the river, output -1.

Otherwise print a single integer, the minimum number of trips needed.

Examples
Input
7 0 2
Output
7
Input
7 7 2
1000000
0100000
0010000
0001000
0000100
0000010
0000001
Output
-1
Input
7 7 7
1000000
0100000
0010000
0001000
0000100
0000010
0000001
Output
1
Input
3 2 1
110
011
Output
7
Note

In the first test, FJ can:

  • Take cows $$$1$$$ and $$$2$$$ to the other side.
  • Return to the starting side.
  • Take cows $$$3$$$ and $$$4$$$ to the other side.
  • Return to the starting side.
  • Take cows $$$5$$$ and $$$6$$$ to the other side.
  • Return to the starting side.
  • Take cow $$$7$$$ the other side.

In total, it takes $$$7$$$ trips. We can show this is optimal.

In the second test, the goal is impossible, since no matter what, FJ must leave at least $$$5$$$ cows on the starting side on his first trip. But no cow can be left on a shore.

In the fourth test, FJ can:

  • Take cow $$$2$$$ to the other side.
  • Return to the starting side.
  • Take cow $$$1$$$ to the other side.
  • Take cow $$$2$$$ back to the starting side.
  • Take cow $$$3$$$ to the other side.
  • Return to the starting side.
  • Take cow $$$2$$$ to the other side for a final time.

In total, it takes $$$7$$$ trips. We can show this is optimal.