Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito y el resto de su equipo están atrapados durante el apocalipsis zombi del 2020. Todos pueden estar afectados y deben encontrar un camino hacia algún hospital para conseguir la cura antes de convertirse en zombis. Los científicos se dieron cuenta que era mejor no luchar contra los zombis si no caminar a hurtadillas a través de ellos. Obviamente los zombis están en todos lados por lo que algunas calles pueden tomar más tiempo que otras. Es también obvio que separarse en menos grupos es mejor para moverse sin ser detectados. Puede ser más dificil también pasar una calle en una dirección que en otra. Cuántos de ustedes pueden pasar a través de los zombis y llegar a un hospital a tiempo ?

Input

En la primera línea tendremos la cantidad de casos. A lo sumo $100$. Luego para cada caso tendremos:

* Una línea con un entero $n$ $(1 \leq n \leq 1000)$: la cantidad de localizaciones en el pueblo.

* Una línea con tres enteros separados por espacio $i$, $g$ y $s$ $(1 \leq i \leq n , 1 \leq g \leq 100, 1 \leq s \leq 100)$: la localización inicial del grupo, la cantidad de personas del grupo y la cantidad de segundos que tienen para llegar a algún hospital, respectivamente.

* Una línea con un entero $m$ $(1 \leq m \leq n)$: la cantidad de hospitales en el pueblo.

* $m$ líneas, cada una con un entero $x$, la localización de cada hospital.

* Una línea con un solo entero $r$ $(0 \leq r \leq 1000)$: la cantidad de calles en el pueblo.

* $r$ líneas, cada una con cuatro enteros $a$, $b$, $p$, $t$ $(1 \leq a, b \leq n, a \neq b, 1 \leq p \leq 100, 1 \leq t \leq 100)$, indicando que hay un camino de $a$ hacia $b$, tal que $p$ personas pueden entrar en cada segundo y toma $t$ segundos en cruzar.

Hay a lo sumo dos caminos –uno en cada dirección– entra cada par de localizaciones. Las localizaciones son lo suficientes seguras como para esperar cualquier cantidad de tiempo y no tienen límite de la cantidad de personas que pueden esperar en ellas.

Output

* Por cada caso una línea con un entero: La mayor cantidad de personas del grupo que pueden llegar a cualquier hospital antes del tiempo $s$.

Sample test(s)