12839번 - 카드 정리 2

태수는 카드 수집가이다. 태수는 카드를 박스에 넣어서 보관한다. 각 박스에는 같은 색 카드만 있어야 한다.

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

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

1. 모든 박스는 비어있거나, 같은 색의 카드만 보관해야 한다.
2. 같은 색을 가진 모든 카드는 모두 같은 박스에 있어야 한다.

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

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

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

• 1 ≤ N ≤ 50
• 1 ≤ M ≤ 14
• M ≤ N
• 박스 하나에 들어있는 같은 색상 카드의 수는 99보다 작거나 같은 음이 아닌 정수이다.