Por Pedro Diogo Machado, UFU Brazil
Hoje em dia, todo mundo adora receber “lemas” de seus amigos no seu celular. Lemas são, geralmente, imagens interessantes com mensagens engraçadas ou que fazem pensar.
A Ultra Repositório South America Lemas é uma companhia de muito sucesso no seu país. De fato, seu sistema de criação de lemas é tão bom que tornou o seu país uma potência mundial nessa ciência.
Para agradar seus clientes, a URSA Lemas envia lemas para seus clientes regularmente, mas essa não é uma tarefa fácil. Cada cliente possui um nível de lemas que ele aprecia, alguns gostam de lemas bem simples, outros preferem os lemas super complicados.
Para facilitar o trabalho de distribuir os lemas para os clientes, a companhia possui uma lista com o nível de complexidade mínimo que cada cliente aprecia. Por exemplo, se o usuário “Felício” tem o nível de complexidade 15, ele vai gostar de lemas de nível 15, 16, 17 e acima, mas não vai gostar de lemas nível 14, 13 ou abaixo pois esses são simples demais pra ele.
Para facilitar o trabalho da “Empresa Grande”, como às vezes é chamada, ela pediu que você criasse um sistema que ajudasse a escolher o nível dos lemas que ela vai enviar aos seus clientes. A empresa vai te fornecer uma lista com o nível de cada cliente e você deve dizer qual é o nível do lema que a empresa deve enviar, de forma que pelos menos um certo número de clientes fique satisfeito com o lema.
Como o sistema demora mais para criar lemas complexos do que lemas simples, o nível que você escolher deve ser o menor possível. É garantido que sempre existirá resposta possível.
A primeira linha da entrada vai conter dois inteiros separados por espaço. O primeiro número N indica a quantidade de clientes que a empresa possui e o segundo número X indica a quantidade mínima de clientes que deve ficar satisfeito com aquele lema.
A segunda linha da entrada vai conter N inteiros separados por espaços, cada um indicando o nível de exigência de um dos clientes da empresa.
(1 \(\le\)X \(\le\) N \(\le\) \(10^5\))
O nível de exigência de um cliente é sempre positivo e pode ser, no máximo, \(10^9\).
A saída deve conter um inteiro representando o menor nível possível de complexidade que um lema deve ter para satisfazer pelo menos X clientes.
Exemplos de Entrada | Exemplos de Saída |
8 4 7 2 5 1 9 4 3 4 |
4 |
5 4 5 2 6 4 1 |
5 |
8 8 7 2 5 1 9 5 10 7 |
10 |