A \(\href{https://algomania.es/account/5}{\color{blue}{\underline{\text{buhsan}}}}\) le gusta mucho la asignatura "Redes de Computadores", así que un día, cuando su profesor propuso un ejercicio extra, él quería ser el primero en resolverlo.
Se considera una sucesión de \(n\) routers, donde cada router está conectado al anterior y al siguiente mediante enlaces idénticos.
El problema consiste en averiguar el tiempo que tarda un paquete en llegar desde un router hasta otro, y ser enviado de vuelta. Para esto, disponemos del tiempo que tarda cada router en procesar el paquete, es decir, el tiempo que tarda en prepararlo para su envío. Además, también disponemos del tiempo que tarda el paquete en ser transmitido a través de cada enlace. Consideramos como despreciable el tiempo que tarda el paquete en ser transmitido a través de la red.
Entrada
La entrada está formada por varias líneas.
La primera línea contiene tres enteros: \(n\), \(t\) y \(q\) - el número de routers, el tiempo de propagación del paquete en cada enlace y el número de consultas, respectivamente.
La segunda línea contiene \(n\) enteros: \(a_1\), \(a_2\), ... \(a_n\) - los tiempos de procesamiento de los routers.
Finalmente, siguen \(q\) líneas, cada una con dos enteros \(u\) y \(v\): el router inicial y final, respectivamente. (\(1 \le u \le v \le n\))
Se garantiza que no habrá más de \(2 \cdot 10^5\) routers, que el tiempo de propagación y el tiempo de procesamiento de cada router no excederá los \(10^9\) segundos.
Salida
Debes imprimir en una sola línea el tiempo total que tarda el paquete en recorrer toda su trayectoria.