The Digital Circuit of Joãozinho
Por Maicon Rafael Zatelli, UFSC 
Brazil
Por Maicon Rafael Zatelli, UFSC Brazil
Joãozinho deseja montar um circuito digital, no qual haverá necessidade de utilizar resistores em série para obter uma determinada resistência equivalente (Req). Joãozinho sabe que a resistência equivalente de resistores em série é a soma das resistências individuais de cada resistor, ou seja, a fórmula para calcular a resistência equivalente de um total de N resistores ligados em série é: Req = R1 + R2 + ... Rn. Mas, Joãozinho ainda não possui os resistores e então ele deve ir na loja do tio Carlinhos comprar resistores. Nesta loja, ele sabe que todos os resistores possuem o mesmo preço independentemente da resistência de cada resistor e a loja também possui uma infinidade de resistores de cada resistência. Obviamente, sabendo disso, ele deseja gastar o mínimo possível para poder montar seu circuito e pediu sua ajuda para criar um programa onde dadas as resistências dos resistores disponíveis na loja, a resistência equivalente desejada por Joãozinho e o preço de um resistor, o programa deve obter o custo mínimo que Joãozinho terá para comprar os resistores para montar o circuito.
A entrada consiste em um conjunto de casos de testes. A primeira linha inicia com um inteiro X (1 ≤ X ≤ 100), que indica a quantidade de casos de testes do conjunto. A seguir, cada caso de teste inicia com três inteiros N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 50.000) e K (1 ≤ K ≤ 10), onde N é a quantidade de resistências diferentes que existem na loja, M é a resistência equivalente que Joãozinho precisa obter para seu circuito, e K é o preço de cada resistor. A seguir existem N linhas, cada uma informando uma resistência ri (1 ≤ ri ≤ 50.000) existente na loja.
Um inteiro com o custo mínimo total que Joãozinho terá para comprar os resistores para seu circuito. Se em algum caso não for possível utilizar os resistores disponíveis na loja para chegar exatamente à resistência equivalente desejada, imprima um único asterisco * como saída.
| Exemplo de Entrada | Exemplo de Saída |
|
2 |
30 |