A healthy menu

시간 제한2초메모리 제한2048 MB

요약

각 반에서 각 과일을 좋아하는 학생 수가 주어질 때, 모든 학생이 과일을 하나 이상 좋아하고 각 반에 학생이 최소 한 명 있다는 조건 아래 학교의 최소 학생 수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 수학, 구현, 정렬
정답자: 아직 제출이 없습니다

문제

At the Institute of Creative Programming Competitions (ICPC), all students love fruits! Knowing this, management decided to conduct a large survey about food preferences to help in preparing the annual menu. To make the survey more professional, they hired the company SBC Research Solutions™, an acronym for “Saladas Bem Científicas”, although some say the name is a tribute to a well-known computer science society...

SBC received the following mission: the school has $M$ classes and offers $N$ different types of fruit. In each class, for each fruit, the number of students who like that fruit was reported.

However, since SBC did not have access to individual student data, nor do they know how many students are in each class, they now need your help! Based only on the survey results (how many students like each fruit in each class), determine the smallest possible number of students the school can have, knowing that the following constraints are satisfied:

each class has at least one student;
each student belongs to a single class;
each student likes at least one fruit;
the same student can like several fruits.

입력

The first line of input contains two integers $N$ and $M$ ( $1 ≤ N, M ≤ 1000$ ), the number of fruits and the number of classes, respectively. Each of the following $N$ lines contains $M$ integers $G\_{i,j}$ , indicating how many students in class $j$ like fruit $i$ ( $0 ≤ G\_{i,j} ≤ 10^6$ for $1 ≤ i ≤ N$ and $1 ≤ j ≤ M$ ).

출력

Your program should print a single line, containing a single integer, the smallest possible number of students in the school, considering the given constraints.

예제2

예제 1
입력
```
3 3
20 15 14
12 20 12
18 5 10
```
예상 출력
```
54
```
예제 2
입력
```
2 3
5 2 4
4 3 6
```
예상 출력
```
14
```