You are given a grid of size NxM , where some of the cells have monsters in them. You have N+M lasers , one at each row and one at each column. You can fire any laser at most once. Assume that these lasers move in a straight line without being blocked by anything. Each monster has a health of 2. In one laser strike, a monster's health is reduced by 1. If monster's health become 0, it dies. You have to find the maximum number of monsters that can be killed if you can fire at most K lasers.
First line contains 3 space separated integers, N, M and K.
Next N lines contains M space separated integers.
Output a single integer denoting the answer.
1 <= N, M <= 20
1 <= K <= N + M
Grid values are 0 (empty cell) and 1 (monster).
Since we can use 6 lasers, we will fire each one of them. All the monsters will be dead.