Problem D
Avoiding the Apocalypse

You and the rest of your team are stuck in a town during the zombie apocalypse of 2020. You all might be infected with the virus and hence you will have to find your way to one of the medical facilities to get a cure before you also become zombies. Because you are scientists you quickly realize that it is safer to try and sneak your way past the zombies than to recklessly start fighting them. Obviously the zombies are everywhere so some streets might take more time to sneak through than others. It is also obvious that by splitting up into smaller groups it is easier to move around undetected.

Furthermore, since these zombies have not mutated to the extent that they actually have eyes in the back of their heads, it might be easy to cross some streets in one direction while hard or impossible to cross them in the other direction.

How many of you can sneak past all the zombies and get to a medical facility in time?

Figure 1: source: xkcd.com/734

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with a single integer $n$ ($1 \leq n \leq 1\, 000$): the number of locations in the town.

• one line with three space-separated integers $i$, $g$ and $s$ ($1 \leq i \leq n$ and $1 \leq g \leq 100$ and $1 \leq s \leq 100$): the starting location of your group, the number of people in it, and the number of time steps you have to get to the safety of a medical facility, respectively.

• one line with a single integer $m$ ($1 \leq m \leq n$): the number of medical facilities in the town.

• $m$ lines, each with a single integer $x$ ($1 \leq x \leq n$): the location of each of the medical facilities.

• one line with a single integer $r$ ($0 \leq r \leq 1\, 000$): the number of roads in the town.

• $r$ lines, each with four space-separated integers $a$, $b$, $p$ and $t$ ($1 \leq a,b \leq n$ and $a \neq b$ and $1 \leq p \leq 100$ and $1 \leq t \leq 100$), indicating that there is a road from $a$ to $b$, which $p$ people can enter at every time step and takes $t$ timesteps to traverse.

There are at most two roads – one in each direction – between any pair of locations. The locations are safe enough to wait at for any amount of time and do not have a limit on the number of people that can be there.

Output

Per test case:

• one line with a single integer: the largest number of people that can get to a medical facility in time.

2
4
3 8 5
2
2
4
5
1 2 1 3
3 2 1 4
3 1 2 1
1 4 1 3
3 4 1 3
4
3 10 5
2
2
4
5
1 2 1 3
3 2 1 4
3 1 2 1
1 4 1 3
3 4 1 3

8
9