teddy online judge

38. Las monedas

Limite de tiempo : 1 seg.   Total runs : 97  Aceptados : 63

Uno de los principales problemas a los que se enfrentan las empresas el día de pago de nómina consiste en determinar el desglose de monedas que habrá de solicitar a la institución bancaria pues se debe optimizar la cantidad mínima de dichas monedas (papel moneda o moneda metálica). Si el pago para un trabajador es de 100 pesos y las monedas que circulan son de 500, 200, 100, 50, 20 10, 5, 2 y 1, entonces deberá solicitar 1 moneda de 100 pesos, ya que de éste modo minimiza la cantidad de las monedas. En el país Monelandia cada año cambian los valores de nominación de las monedas circulantes por lo que las empresas desean un programa que con base a los pagos que deben realizar se determine el monto óptimo de monedas que deberá solicitar a la institución bancaria.

Entrada

Un archivo cuya primera fila indica el número de pagos (N) a realizar, en la segunda fila el número que indica la cantidad de monedas circulantes (M) para ese periodo de pago, los siguientes N renglones contienen las cantidades a pagar a cada empleado (1<=P<=300,000), y los siguientes M renglones indican cada uno el valor en orden ascendente de las monedas vigentes.

Salida

Un archivo en el que cada renglón indique la cantidad y el valor de la moneda en orden descendente para hacer el pago de nómina, si una moneda no se requiere entonces deberá ser omitida.

Ejemplo de entrada (data.in)

2
10
1499
1051
1
5
10
20
40
80
170
350
700
1400

Ejemplo de salida (data.out)

1 1400
1 700
1 350
1 80
1 10
1 5
5 1