Contendo Água
O Grupo de Engenharia, Modernização e Projeto de Represas Otimizadas possui várias represas de água distribuídas pelo país.
Naturalmente, as represas precisam ser capazes de conter o máximo de água possível. O grupo precisa da sua ajuda para descobrir o máximo de água que pode ser contida em suas represas, depois de alterações.
Você é dado o mapa de uma das represas no formato de um array, identificando a altura da represa em cada posição. O orçamento do grupo permite fazer no máximo operações do tipo: escolher uma posição, e incrementar a altura da represa nesta posição em .
Input
A primeira linha do input contém dois números: (), e (), o tamanho do mapa da represa, e o número de operações permitidas pelo orçamento do grupo.
A segunda linha do input contém inteiros (), as alturas de cada posição da represa.
Output
Imprima um único inteiro: A altura da maior quantidade de água que a represa consegue conter.
Samples
Sample 1
Input
5 3 5 2 1 3 7
Output
3
A melhor opção é incrementar a segunda posição uma vez, e a terceira posição duas vezes, obtendo: , que pode conter água até uma altura igual a 3.