Exercício 5
Bolo de rolo
Juvenal adora bolo de rolo, embora não seja pernambucano. Na sua terra, essa iguaria é conhecida como rocambole. Bolo de rolo é uma excelente opção de lanche para encontros entre amigos ou ocasiões com mais pessoas. No entanto, há o problema da gula das pessoas - elas acabam pegando pedaços maiores que os pedaços dos outros. Para sua próxima festa, Juvenal pensa em providenciar bolo de rolo para os convidados, porém tais problemas os fizeram desistir dessa idéia.
Embora a solução tenha sido momentaneamente abandonada, uma idéia simples surgiu: cortar previamente o bolo em fatias de tamanho iguais e distribuí-las entre as pessoas. O único problema com tal idéia é que se o número de pessoas for muito grande, fica impraticável ter apenas um bolo de rolo. Por exemplo, se quisermos que 1.000 pessoas recebam 20 centímetros de bolo de rolo, seria necessário um bolo de 20.000 centímetros, ou 200 metros!
Um amigo de Juvenal, que faz BSI, levantou a seguinte hipótese: se houvesse N pessoas e fossem encomendados K bolos de padarias diferentes, cada qual com uma determinada metragem (tamanho) Mi (1 ≤ i ≤ K), seria possível retirar desses bolos N fatias de mesmo tamanho, possivelmente sobrando partes não utilizadas. A questão seria: qual o tamanho inteiro máximo que essas fatias poderão ter?
Por exemplo, se tivermos K = 4, com os tamanhos (em centímetros) M1 = 120, M2 = 89, M3 = 230 e M4 = 177 e N = 10, podemos retirar N fatias iguais de tamanho máximo 57, pois assim conseguimos 2 fatias no primeiro bolo de rolo, 1 no segundo, 4 no terceiro e 3 no quarto, totalizando as 10 fatias necessárias. Se tentarmos cortar fatias de tamanho 58, só será possível obter 3 fatias do terceiro bolo, totalizando 9 e, portanto, 57 é realmente o melhor que podemos obter. Note que não podemos usar duas ou mais fatias menores de diferentes bolos para formarmos uma fatia do tamanho selecionado. (ficaria muito deselegante dar um lanche recortado às pessoas).
Tarefa
Escreva um programa que, dados os tamanhos de bolo de rolo disponíveis (em centímetros) e a quantidade de pessoas a serem atendidas, retorne o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.
Entrada
A entrada contém um único conjunto de testes. A primeira linha da entrada contém um inteiro N que indica a quantidade pessoas (1 ≤ N ≤ 10.000). A segunda linha contém um inteiro K (1 ≤ K ≤ 10.000) que é a quantidade de bolos disponível. Na terceira linha há K inteiros M (1 ≤ M ≤ 10.000) separados por um espaço em branco representando o tamanho de cada bolo de rolo.
Saída
Seu programa deve imprimir uma única linha, contendo o tamanho inteiro máximo da fatia que pode ser cortada.
Exemplos
Entrada
10
4
120 89 230 177
Saída
57
\\cursor aqui
Entrada
3
2
45 85
Saída
42
\\cursor aqui
Entrada
7
7
100 98 99 505 102 97 101
Saída
101
\\cursor aqui