Amadas por alguns e odiadas por muitos, as moedas estão em toda parte e fazem parte do cotidiano de qualquer pessoa. Isso acontece pois, afinal, guardadas as devidas proporções, elas representam dinheiro tanto quanto as notas.
Sua tarefa neste problema é elaborar um programa que ajude os diversos estabelecimentos comerciais a fornecer um valor de troco com o menor número de moedas possível. Visando a globalização da economia, seu programa deve ser capaz de trabalhar com moedas de diversos países. Um país por vez, no entanto.
Para que você possa realizar sua tarefa, serão fornecidos n inteiros positivos que representam os valores das moedas em circulação em um determinado país e uma coleção de m inteiros positivos que representam os valores para os quais você deverá calcular o equivalente em moedas. Sabe-se que o país com mais moedas no mundo é o Schredzistitão do Sul, que tem 100 moedas. Como dissemos anteriormente, sua resposta deve envolver o menor número possível de moedas. Pode acontecer o caso de existir mais de uma configuração possível, isto é, pelo menos duas formas de combinar o mesmo número de moedas para atingir o valor desejado. Nesse caso, seu programa deve escolher a configuração que possua o maior número de moedas de mais alto valor.
Você deve observar também que, em alguns casos, dependendo dos valores das moedas e do troco desejado, pode ser impossível encontrar uma configuração adequada.