Canadian Computing Competition: 2007 Stage 2, Day 2, Problem 1

Politicians like to get elected. They will do just about anything to get elected. Including changing the rules of the voting: who can vote, where you can vote, when you can vote, etc. One very common practice is called gerrymandering, where the boundaries of "ridings" are redrawn to favour a particular candidate (the one doing the redrawing, of course).

Your task is to help determine how to do some simple, linear gerrymandering.

You will be given the information about $N$ ridings $(2\le N\le 100000)$ where there are candidates from $p$ $(2\le p\le 10)$ different parties. These $N$ ridings are linear, in the sense that they are side-by-side; there are two ridings (on the ends) that have only one adjacent riding, with the rest of the ridings having two adjacent ridings. A picture is shown below for $N=4$ and $p=2$ (which is also the sample data):

Note that Riding 1 and Riding 2 are adjacent, Riding 2 and 3 are adjacent, Riding 3 and 4 are adjacent. No other ridings are adjacent.

You have some financial backing that will let you bribe the people in charge of setting the boundaries of ridings: in particular, there is a fixed rate to merge two adjacent boundaries. When you merge two ridings, the votes of the ridings merge together, in the sense that the number of votes of party 1 is the sum of the votes of party 1 in each riding, and likewise for all other parties.

Your task is to merge the minimum number of regions such that the first party (your party!) has a majority of the ridings. Note that to win a riding, the party must have more votes than any other party in that riding. Also note that to have a majority of ridings, if there are $Q$ ridings (where $Q\le N$), then your party has won at least $\lfloor \frac{Q}{2}\rfloor +1$ of the ridings.

Input Specification

The first line of input will consist of the integer $N$. The second line of input will consist of the integer $p$. The next $N$ lines will each contain $p$ non-negative integers (where each integer is at most $10000$), separated by one space character. Specifically, the $p$ integers on each line are $v_1,v_2\dots v_p$ where $v_1$ is the number of votes that party $1$ will receive in this riding, $v_2$ is the number of votes that party $2$ will receive in this riding, etc.

You may also assume that the total number of voters is less than 2 billion.

Output Specification

One line, consisting of an integer, which gives the minimum number of ridings that need to be merged in order for the first party to win a majority of ridings. If the first party cannot win, even with any number of mergers, output -1.

Sample Input 1

4
2
1 5
4 3
1 2
6 1

Sample Output 1

1

Sample Input 2

3
3
2 0 1
1 3 0
0 0 1

Sample Output 2

-1