All Tracks Basic Programming Bit Manipulation Basics of Bit Manipulation Problem

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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications