Zombie Apocalypse

The year is 2020. You and your group are trapped in a town inside a city that zombies have wrecked. Your group is already infected, so you have to reach a hospital and get treated before you turn. Everyone in the group is a scientist, so sneaking past the zombies is safer than charging at them to force a way through. Zombies are everywhere, and on some roads sneaking through takes longer than on others. Splitting into several groups that move on their own is sometimes far safer than travelling together.

The infection did not go far enough to give these zombies eyes in the back of their heads. On some roads one direction is easy to sneak along while going back the other way is hard or impossible.

Find the largest number of people in your group who can avoid the zombies and reach a hospital before they turn.

The first line holds the number of test cases. Each test case has the form below. Every value is an integer.

• The first line holds the number of places $n$. ($1 \le n \le 1000$)
• The next line holds the place $i$ where the group starts, the number of people $g$ in the group, and the time $s$ it takes to turn into a zombie. ($1 \le i \le n$, $1 \le g \le 100$, $1 \le s \le 100$)
  • Someone who reaches a hospital at time $s$ has found it before turning.
• The next line holds the number of hospitals $m$. ($1 \le m \le n$)
• Each of the next $m$ lines holds the number $x$ of a place that has a hospital. ($1 \le x \le n$)
• The next line holds the number of roads $r$. ($0 \le r \le 1000$)
• Each of the next $r$ lines holds the road values $a$, $b$, $p$, $t$. ($1 \le a, b \le n$, $a \ne b$, $1 \le p \le 100$, $1 \le t \le 100$) The road runs from $a$ to $b$, at most $p$ people step onto it at each unit of time, and crossing it takes $t$ units of time.

The group is at place $i$ at time $0$. People step onto a road at integer times, and someone who steps onto a road at time $\tau$ arrives at the far place at time $\tau + t$.

Between any pair of places there are at most 2 roads, one per direction. Every place is safe enough to stand and wait in for as long as you like, and there is no limit on how many people a place holds.

For each test case, print on its own line the largest number of people who reach a hospital without being infected.