34749번 - A healthy menu 다국어

문제

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.

제한

노트