Día nublado
Durante todo el año el país donde vive el ogro Ork está cubierto de nubes. El país está compuesto por pueblos, situados en una línea unidimensional. Las posiciones de cada uno de los pueblos son conocidas por Ork, así como la cantidad de ogros que viven en cada uno de ellos. Cada nube se encuentra en una posición y cubre todas las pueblos situados a cierta distancia de ella. En otras palabras la nube cubre el rango
El clima en un pueblo está nublado, si este se encuentra en el rango de al menos una nube. De lo contrario el clima es soleado.
Todos sabemos que el ogro Ork tiene poderes mágicos con los cuales es capaz de desaparecer exactamente una nube. Él quiere desaparecer una nube de tal manera que la mayor cantidad de ogros tengan clima soleado en sus pueblos.
Entrada
La primera línea de entrada contiene un entero , la cantidad de pueblos.
La segunda línea contiene enteros separados por espacios, el -ésimo número representa la cantidad de ogros que viven en el -ésimo pueblo.
La tercera línea contiene enteros separados por espacios, el -ésimo número representa la posición del -ésimo pueblo.
La cuarta línea contiene un entero , la cantidad de nubes.
La quinta línea contiene enteros separados por espacios, el -ésimo número representa la posición de la -ésima nube.
La sexta línea contiene enteros separados por espacios, el -ésimo número representa el rango de la -ésima nube.
Salida
La única línea de salida debe contener un solo entero que representa la cantidad de personas que estarán en pueblos soleados, si Ork desaparece exactamente una nube.
Ejemplo de Entrada
2
10 100
5 100
1
4
1
Ejemplo de Salida
110
Explicación del Ejemplo
En el ejemplo solo hay una nube que cubre el primer pueblo. La única opción es desaparecerla y todos los pueblos quedarán soleados, por lo que todos los ogros tendrán clima soleado en sus pueblos.
Comments