cho.sh
Notes
Loading...

Card Organization 1

Time limit

2s

Memory limit

128 MB

Problem

Taesu collects cards and stores them in boxes. One day, his younger sibling played with the cards and put them back into the boxes without following Taesu's ordering rule, so Taesu wants to organize them again.

There are N boxes and M different card colors. Taesu wants the boxes to satisfy these conditions:

  1. At most one box may be designated as the joker box. The joker box may contain cards of different colors.
  2. Every box except the joker box must be empty or contain cards of only one color.
  3. For each color, all cards of that color must be in the same non-joker box, excluding cards in the joker box. It is also allowed for all cards of a color to be in the joker box.

For each box, you are given how many cards of each color it contains. Find the minimum number of moves needed to satisfy the conditions. One move means taking one or more cards from one box and putting them into another box; the cards taken in a single move do not have to be the same color.

Input

The first line contains the number of boxes N and the number of card colors M.

Each of the next N lines contains information about one box. Each line has M integers: the number of cards of color 1, color 2, ..., color M, in that order.

Output

Print the minimum number of moves needed to make the boxes satisfy the conditions.

Constraints

  • 1 <= N, M <= 50
  • In one box, the number of cards of any one color is at most 9.