Como es la Semana Aniversario de la Carrera de Informatica y tu eres uno de los organizadores de dicho evento estas buscando un juego para poder presentarlo, para así que puedan participar todos los estudiantes.

Estás jugando un famoso video juego (que simplemente funciona) donde tienes varias habilidades que puedes mejorar. 

Hoy te enfocaste en la habilidad de "Forja". Tu táctica es obvia: forjar armas a partir de lingotes y luego fundirlas para recuperar parcialmente los materiales. Para simplificar, cada vez que creas un objeto, obtienes 1 punto de experiencia, y cada vez que fundes un objeto, también obtienes 1 punto de experiencia. Hay \( n \) clases de armas que puedes forjar y \( m \) tipos de lingotes de metal. Puedes crear un arma de la \( i \)-ésima clase, gastando \( a_i \) lingotes de metal del mismo tipo. Fundir un arma de la \( i \)-ésima clase (que habías fabricado anteriormente) te devuelve \( b_i \) lingotes del tipo de metal del que estaba hecha. Tienes \( c_j \) lingotes de metal del \( j \)-ésimo tipo, y sabes que puedes fabricar un arma de cualquier clase con cualquier tipo de metal. Cada combinación de una clase de arma y un tipo de metal se puede usar un número ilimitado de veces.

La primera línea contiene dos enteros \( n \) y \( m \) (\( 1 \leq n, m \leq 10^6 \)) — el número de clases de armas y tipos de metales. La segunda línea contiene \( n \) enteros \( a_1, a_2, \dots, a_n \) (\( 1 \leq a_i \leq 10^6 \)), donde \( a_i \) es el número de lingotes que necesitas para forjar un arma de la \( i \)-ésima clase. La tercera línea contiene \( n \) enteros \( b_1, b_2, \dots, b_n \) (\( 0 \leq b_i < a_i \)), donde \( b_i \) es el número de lingotes que recuperas al fundir un arma de la \( i \)-ésima clase que habías forjado anteriormente. La cuarta línea contiene \( m \) enteros \( c_1, c_2, \dots, c_m \) (\( 1 \leq c_j \leq 10^9 \)) — el número de lingotes que tienes del tipo de metal correspondiente.

Imprime un entero — la cantidad máxima total de puntos de experiencia que puedes ganar forjando y fundiendo armas repetidamente.

En el primer ejemplo, puedes hacer lo siguiente:

1. Forjar un arma de la 1ª clase con el 1º tipo de metal, gastando 9 lingotes.
2. Fundir esa arma, recuperando 8 lingotes del 1º tipo de metal.
3. Nuevamente, forjar y fundir un arma de la 1ª clase con el 1º tipo de metal.
4. Forjar y fundir un arma de la 3ª clase con el 1º tipo de metal.
5. Forjar y fundir un arma de la 3ª clase con el 3º tipo de metal.
6. Forjar y fundir un arma de la 4ª clase con el 1º tipo de metal.
7. Forjar y fundir un arma de la 5ª clase con el 3º tipo de metal.

Al final, tendrás $c = [2, 4, 2]$ lingotes restantes. En total, has forjado 6 armas y fundido 6 armas, obteniendo 12 puntos de experiencia en total.