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, seguido de P enteros p_1, p_2, \ldots, p_P que representan las cantidades de panes en los P paquetes de pan disponibles. En la segunda línea aparece el entero S, el número de paquetes de salchichas disponibles. A continuación S enteros s_1, s_2, \ldots, s_S 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.

Restricciones

  • 0 \leq P \leq 100
  • 1 \leq P_i \leq 1000
  • 0 \leq S \leq 100
  • 1 \leq S_i \leq 1000

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 2 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.