Monsters in Grid
Tag(s):

## Basic Programming, Medium

Problem
Editorial
Analytics

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.

Input:
First line contains 3 space separated integers, N, M and K.
Next N lines contains M space separated integers.

Output
Output a single integer denoting the answer.

Constraints
1 <= N, M <= 20
1 <= K <= N + M
Grid values are 0 (empty cell) and 1 (monster).

SAMPLE INPUT
3 3 6
0 0 1
0 1 0
1 1 1

SAMPLE OUTPUT
5

Explanation

Since we can use 6 lasers, we will fire each one of them. All the monsters will be dead.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Sorting
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Math > Linear Algebra
• Algorithms > Searching
• Algorithms > Dynamic Programming