시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB351976829.060%

문제

태수는 카드 수집가이다. 태수는 카드를 박스에 넣어서 보관한다. 어느날, 태수의 동생이 태수의 카드를 가지고 놀았고, 박스에 다시 넣어두었다. 하지만, 태수가 넣는 기준을 지켜서 넣은 것이 아니기 때문에, 태수는 카드를 다시 정리하려고 한다.

박스는 N개가 있고, 카드는 색상으로 구분할 수 있다. 서로 다른 색상의 수는 M개가 있다. 태수는 아래 조건을 지키게 하기 위해 카드를 정리하려고 한다.

  1. 박스 최대 1개는 조커 박스로 지정할 수 있다. 조커 박스는 색이 다른 카드를 보관해도 된다. 
  2. 조커 박스를 제외한 모든 박스는 비어있거나, 같은 색의 카드만 보관해야 한다.
  3. 같은 색을 가진 모든 카드는 모두 같은 박스에 있어야 한다. 이때 조커 박스에 들어있는 카드는 제외한다. 같은 색을 가진 모든 카드가 조커 박스에 들어있는 것도 가능하다.

각각의 박스에 각 색상을 가진 카드가 몇 장 들어있는지 입력으로 주어진다. 이때 최소 몇 번 이동해서 위의 조건을 지키게 할 수 있는지 구해보자. 이동 한 번은 한 박스에서 1장 이상의 카드를 빼 다른 박스에 넣는 것을 의미하며, 빼낸 카드의 색상은 같지 않아도 된다.

입력

첫째 줄에 박스의 개수 N과 카드 색상의 개수 M이 주어진다. 둘째 줄부터 N개의 줄에 한 박스에 들어있는 카드의 정보가 주어진다. 카드의 정보는 M개의 정수로 이루어져 있고, 첫 정수부터 1번 색상 카드의 수, 2번 색상 카드의 수, ..., M번 색상 카드의 수이다.

출력

첫째 줄에 문제의 조건을 지키게 하기 위한 최소 이동 횟수를 구해보자.

제한

  • 1 ≤ N, M ≤ 50
  • 박스 하나에 들어있는 같은 색상 카드의 수는 최대 9장이다.

예제 입력 1

3 2
1 1
1 1
1 0

예제 출력 1

1

예제 입력 2

2 2
2 0
1 1

예제 출력 2

0

예제 입력 3

4 2
1 0
1 0
0 1
0 1

예제 출력 3

1

예제 입력 4

6 2
1 1
1 1
1 1
1 0
1 0
0 1

예제 출력 4

3

예제 입력 5

11 12
0 2 0 0 0 8 0 0 0 0 7 0
0 0 0 0 0 4 0 0 0 0 0 0
0 6 0 0 0 0 6 0 0 0 0 0
0 0 6 0 0 0 0 0 0 3 6 2
0 0 0 7 2 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0 0 0 0 0
0 0 4 0 0 9 0 0 3 0 0 0
0 0 0 8 0 0 0 0 0 0 0 0
0 2 0 0 3 0 0 0 3 0 0 0
0 0 0 5 0 0 2 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0 0 0

예제 출력 5

6

출처