Comprando Alimentos.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++

En IslaGrande hay dos tipos de alimentos, pan y salchicha, que se venden en paquetes separados donde cada paquete contiene cierta cantidad de unidades del tipo de alimento correspondiente. Por ejemplo: en la tienda hay dispobibles paquetes de pan con 3, 5, 5, 7 y 10 unidades; así como paquetes de 4, 4 y 13 unidades de salchichas. Note que estos números representan solo las cantidades disponibles en el momento que usted acude a realizar la compra, o sea, usted no puede comprar 14 panes puesto que no hay manera de lograr esa cantidad con los paquetes disponibles, por otra parte si es posible adquirir 8 panes (el paquete de 3 y uno de 5) ó 15 panes (10 + 5; 3 + 7 + 5); de igual modo sucede con las salchichas, solo puedes adquirir estas cantidades: 4, 8, 13, 17 y 21.

Pero hay que emparejar los dos productos de modo que la merienda siempre sea pan con salchicha y es necesario hacerlo comprando la menor cantidad de paquetes. El mínimo requerido para el ejemplo de arriba es 3 paquetes: los paquetes de 3 y 10 panes junto con el paquete de 13 salchichas.

Entrada

La primera línea de la entrada contiene un entero P (0 \leq P \leq 100), seguido de P enteros p_1, p_2, ..., p_P   (1 \leq P_i \leq 1000) que representan las cantidades de panes en los P paquetes de pan disponibles. En la segunda línea aparece el entero S (0 \leq S \leq 100), el número de paquetes de salchichas disponibles. A continuación S enteros s_1, s_2, ..., s_S (1 \leq S_i \leq 1000) que representan las cantidades de los paquetes de salchichas.

Salida

Imprima un único entero que representa la mínima cantidad de paquetes que debes comprar para asegurar emparejar los panes y las salchichas sin que sobren unidades de algún alimento. O imprime la palabra "imposible" sin comillas si tal compra no puede realizarse.

Ejemplo #1 de Entrada

4 10 10 10 10
10 8 8 8 12 12 12 8 8 12 12

Ejemplo #1 de Salida

4

Explicación del primer ejemplo: escoja 2 paquetes de panes y dos de salchichas, uno de 8 y otro de 12, de este modo logra 20 unidades de cada tipo de alimento.

Ejemplo #2 de Entrada

4 7 7 14 7
3 11 22 11

Ejemplo #2 de Salida

imposible

Comments

There are no comments at the moment.