Concurso

Nome do arquivo: concurso.x, onde x deve ser c, cpp, java, js ou py
Fonte: OBI2024

Cláudia trabalha na OBI (Organização dos Bons Informáticos), que recentemente realizou um concurso para contratar novos funcionários. Agora, Cláudia tem a tarefa de determinar a nota de corte para o concurso.

Chamamos de nota de corte a nota mínima necessária para ser aprovado no concurso. Ou seja, se a nota de corte do concurso for C, então todos os participantes com uma nota maior ou igual a C serão aprovados no concurso e todos com nota menor que C serão reprovados.

Seu chefe pediu para que Cláudia aprove no mínimo K candidatos do concurso para a próxima fase, mas ela também não quer que a nota de corte seja muito baixa. Por isso, Cláudia decidiu que a nota de corte deverá ser a maior nota C que faz com que no mínimo K candidatos sejam aprovados.

Sua tarefa é: dados o número N de candidatos, as notas A1, A2, …, An dos candidatos e a quantidade mínima de aprovados K, diga qual deve ser a maior nota de corte C para que pelo menos K candidatos sejam aprovados.

A primeira linha da entrada contém dois inteiros, N e K, representando, respectivamente, o número de participantes e o número mínimo de candidatos que devem ser aprovados.

A segunda linha da entrada contém N inteiros Ai, representando as notas dos participantes.

Seu programa deve imprimir uma linha contendo um único inteiro C, a nota de corte que deve ser escolhida por Cláudia.

• 1 ≤ K ≤ N ≤ 500
• 1 ≤ Ai ≤ 100 para todo 1 ≤ i ≤ N

A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima.

• Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados aabixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
• Subtarefa 2 (20 pontos): K = 1
• Subtarefa 3 (20 pontos): K = 3
• Subtarefa 4 (20 pontos): Ai ≤ 2
• Subtarefa 5 (40 pontos): Sem restrições adicionais.

Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as sutarefas resolvidas corretamente por qualquer uma das suas submissões.

Explicação do exemplo 1: Neste caso temos 3 candidatos com notas 92, 83 e 98 e Cláudia deseja aprovar no mínimo 1 candidato. A maior nota de corte possível para que alguém seja aprovado é 98, a nota do melhor candidato.

Explicação do exemplo 2: A maior nota de corte possível para que 2 candidatos sejam aprovados é 3. Neste caso, os candidatos com nota 3 e 4 serão aprovados.

Explicação do exemplo 3: Para que pelo menos 3 candidatos sejam aprovados, a nota de corte deve ser no mínimo 20.