AlgoMarket

Necesito que me hagas la compra. Para empezar, mi supermercado de confianza se llama AlgoMarket. Después de que entres por la puerta y saludes al dependiente, vas a ver $n$ artículos diferentes. Algo que hace especial a este supermercado es que no existe ningún límite en la cantidad de unidades que puedes comprar de cualquier artículo. Una vez te hayas familiarizado con todos los productos, debes ir al mostrador, donde encontrarás el catálogo de la tienda y verás que el precio del $i$-ésimo artículo es de $a_i$ monedas. Mi lista de la compra es muy específica, por lo que necesito exactamente $b_i$ unidades de cada artículo. Con la inflación, AlgoMarket se ha visto obligado a subir los precios, pero por suerte (o por desgracia para ti), hay ofertas especiales. Tras preguntarle amablemente al dependiente, te darás cuenta que tienes a tu disposición $m$ ofertas que puedes repetir tantas veces como quieras: el precio de la $i$-ésima oferta es de $c_i$ monedas y, al comprarla, obtienes $d_{i, j}$ unidades del $j$-ésimo artículo de la tienda. ¿Sabrías decirme el número mínimo de monedas que necesito para hacer la compra? ## Enunciado La entrada consiste en varios casos de prueba. Para cada caso de prueba: - Una línea con un entero $n$ ($1 \le n \le 6$) - el número de artículos diferentes en la tienda. - Una línea con $n$ enteros $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 1000$) - el precio de cada artículo individual en monedas. - Una línea con $n$ enteros $b_1$, $b_2$, ..., $b_n$ ($0 \le b_i \le 10$) - la cantidad exacta de unidades que se deben comprar de cada artículo. - Una línea con un entero $m$ ($0 \le m \le 100$) - el número de ofertas disponibles. - Una línea con $m$ enteros $c_1$, $c_2$, ..., $c_n$ ($1 \le c_i \le 1000$) - el precio de cada oferta en monedas. - Siguen $m$ líneas, cada una con $n$ enteros $d_{i, 1}$, $d_{i, 2}$, ..., $d_{i, n}$ ($0 \le d_{i, j} \le 10$)- la cantidad de cada artículo que se obtiene al comprar la $i$-ésima oferta. ## Salida Para caso de prueba, imprime el número mínimo de monedas que necesitas para hacer la compra exacta que te pido.

2
2 5
3 2
2
5 10
3 0
1 2
2
5 2
13 1
0

14
67