Sereja has an n × m rectangular table a, each cell of the table contains a zero or a number one. Sereja wants his table to meet the following requirement: each connected component of the same values forms a rectangle with sides parallel to the sides of the table. Rectangles should be filled with cells, that is, if a component form a rectangle of size h × w, then the component must contain exactly hw cells.

A connected component of the same values is a set of cells of the table that meet the following conditions:  every two cells of the set have the same value;  the cells of the set form a connected region on the table (two cells are connected if they are adjacent in some row or some column of the table);  it is impossible to add any cell to the set unless we violate the two previous conditions. 

Can Sereja change the values of at most k cells of the table so that the table met the described requirement? What minimum number of table cells should he change in this case?


-----Input-----

The first line contains integers n, m and k (1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10). Next n lines describe the table a: the i-th of them contains m integers a_{i}1, a_{i}2, ..., a_{im} (0 ≤ a_{i}, j ≤ 1) — the values in the cells of the i-th row.


-----Output-----

Print -1, if it is impossible to meet the requirement. Otherwise, print the minimum number of cells which should be changed.


-----Examples-----
Input
5 5 2
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1

Output
1

Input
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0

Output
-1

Input
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1

Output
0

Difficulty: competition

Starter code:

Solutions:
read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = []
for y in a:
    x = 0
    for b in y:
        x = 2 * x + b
    xs.append(x)

def work(y):
    tot = 0
    for x in xs:
        c = bin(x ^ y).count('1')
        tot += min(c, m - c)
    return tot

ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)


from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)


from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)


from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)



from functools import *

read_line = lambda: [int(i) for i in input().split()]

n, m, k = read_line()
a = [read_line() for i in range(n)]
if n < m:
    n, m, a = m, n, list(zip(*a))

xs = [reduce(lambda x, b: 2 * x + b, y) for y in a]
minm = lambda a: min(a, m - a)
work = lambda y: sum(minm(bin(x ^ y).count('1')) for x in xs)
ans = min(list(map(work, xs if m > k else list(range(1<<m)))))

print(ans if ans <= k else -1)




# Made By Mostafa_Khaled