All Tracks Problem

Benny and City
Tag(s):

Bitmask, Brute-force search, Medium

Problem
Editorial
Analytics

View Russian Translation

From the beginning Benny was a very harsh pig.

She lives in a huge city. City can be determined as a grid with N lines and M columns. The city contains some houses. Each house has it's own beauty. Beauty of house at point(i, j) is Ai, j.

To make city more beautiful Benny decides to destroy some houses. If Benny has destroyed COUNT lines and columns of the city in total and sum of beauty of not destroyed houses is SUM then the beauty of the city is SUM - COUNT * C. Where C is some integer, called coefficient of destruction.

Benny is going to destroy houses in such way: She chooses some line or column and destroy all houses in this line or column.

You task in to find the maximum beauty of the city that Benny can reach after destroying some houses.

Input format

The first line contains three integers N, M, C. The following N lines contain M integers Ai, j denoting the beauty of the house at point(i, j).

Output format

Print only one integer - maximal beauty of the city that Benny can reach by destroying some houses.

Constraints

  • 1 ≤ N, M ≤ 20
  • 0 ≤ C ≤ 1000
  • -10000 ≤ Ai, j ≤ 10000
  • 2 ≤ N + M ≤ 20 holds for test cases worth 20% of the problem's score.

Sample Explanation

You have to destroy only first line and then the result beauty of the city will be 2.

SAMPLE INPUT
3 3 2
-1 1 -2
-1 -1 2
6 -1 -1
SAMPLE OUTPUT
2
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: Bash, 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?