uCoder | 1263 | Nível: 5 | Tempo Limite: 4
Prefeito Tecnológico
Adaptado por Erich Rodrigues
Competição: Interfatecs 2016 1ª Fase
Estocolmo na Suécia é conhecida por ser uma das cidades mais tecnológicas do mundo. Aproveitando esse viés tecnológico da cidade, o prefeito teve uma brilhante ideia. Ele decidiu criar um aplicativo para smartphones em que a população pode votar quais as melhorias da cidade devem ter mais prioridade para serem implementadas pela administração pública. Com isso, ele espera que a população fique mais satisfeita com o seu mandato, e consequentemente, consiga se reeleger nas próximas eleições.
O aplicativo é simples. As pessoas se cadastram e vêm uma lista das possíveis melhorias que podem ser realizadas pela prefeitura na cidade. Cada pessoa pode selecionar uma única melhoria que mais lhe agrada e efetuar o voto. Depois de um período fixo de votação, o prefeito e seus assessores vão realizar as melhorias de acordo com o seu custo e quantidade de votos recebidos pelo aplicativo.
Antes de contratar o programador responsável pelo desenvolvimento do aplicativo, o prefeito sugeriu que pré-projetos com o algoritmo principal para a solução do problema fossem enviados para uma seleção inicial e você, que sonha em sair do Brasil, decidiu arriscar.
Entrada
A primeira linha de entrada contém o número de casos de teste N (1 ≤ N ≤ 50). Cada caso de teste inicia com uma linha contendo dois inteiros, T (1 ≤ T ≤ 100) e L (1 ≤ L ≤ 100), separados por um espaço em branco, que representam o total (em milhões) em caixa da prefeitura para a implementação das melhorias e o número de itens da lista de melhorias, respectivamente. As L linhas seguintes, contêm um inteiro C (1 ≤ C ≤ 100), indicando o custo total (em milhões) para implementar aquela melhoria; e um inteiro V (1 ≤ V ≤ 1000) indicando a quantidade de votos (em milhares) que aquela melhoria recebeu, ambos separados por um espaço em branco.
Saída
Para cada caso de teste, imprima uma linha contendo o maior número de votos atendidos e a quantidade de dinheiro que vai sobrar em caixa, ambos separados por um espaço em branco. Caso não seja possível atender nenhuma melhoria imprima “NO FUNDS” (sem aspas).
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
3 |
1250 5 |