Alimentação saudável
No Instituto de Competição em Programação Criativa (ICPC), todos os alunos adoram frutas! Sabendo disso, a direção decidiu realizar uma grande pesquisa sobre preferências alimentares para ajudar na elaboração do cardápio anual. Para tornar o levantamento mais profissional, contrataram a empresa SBC Research Solutions™, sigla para “Saladas Bem Cientı́ficas”, embora alguns digam que o nome seja homenagem a uma conhecida sociedade de computação...
A SBC recebeu a seguinte missão: a escola tem M turmas e oferece N tipos diferentes de frutas. Em cada turma, para cada fruta, foi informado o número de alunos que gostam daquela fruta.
Contudo, como a SBC não teve acesso aos dados individuais dos alunos, nem sabe quantos alunos há em cada turma, precisa agora de sua ajuda! Com base apenas nos resultados da pesquisa (quantos alunos gostam de cada fruta em cada turma), determine o menor número possı́vel de alunos que a escola pode ter, sabendo que as seguintes restrições são obedecidas:
- cada turma tem pelo menos um aluno;
- cada aluno pertence a uma única turma;
- cada aluno gosta de pelo menos uma fruta;
- um mesmo aluno pode gostar de várias frutas.
Input
A primeira linha contém dois inteiros $N$ e $M$ $(1 ≤ N, M ≤ 1000)$, respectivamente o número de frutas e o número de turmas. Cada uma das $N$ linhas seguintes contém $M$ inteiros $G_{i,j}$ , indicando quantos alunos da turma $j$ gostam da fruta $i$ $(0 ≤ Gi,j ≤ 10^6$ para $1 ≤ i ≤ N$ e $1 ≤ j ≤ M )$.
Output
Seu programa deve produzir uma única linha, contendo um único inteiro, o menor número possı́vel de alunos na escola, considerando as restrições dadas.
3 3 20 15 14 12 20 12 18 5 10
54
2 3 5 2 4 4 3 6
14