좀비 아포칼립스

2020년, 당신과 일행은 좀비가 휩쓸고 간 대도시의 한 마을에 갇혔다. 일행도 이미 바이러스에 감염되었기 때문에 좀비가 되기 전에 병원을 찾아 치료를 받아야 한다. 일행은 모두 과학자라서, 좀비에게 정면으로 돌격해 길을 뚫기보다 몰래 움직이는 쪽이 안전하다고 판단했다. 그런데 좀비가 온 사방에 깔려 있어서 어떤 도로는 몰래 지나가는 데 시간이 더 걸린다. 다 같이 몰려다니기보다 여러 무리로 나뉘어 각자 나아가는 편이 훨씬 안전할 때도 있다.

이 좀비들은 감염이 심하지 않아서 머리 뒤에 눈이 달려 있지는 않다. 그래서 어떤 도로는 한쪽 방향으로 지나가기는 쉬워도 반대로 거슬러 가기는 어렵거나 불가능하다.

일행 중 최대 몇 명이 좀비가 되기 전에 좀비를 피해 병원에 도착할 수 있는지 구하라.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 이루어진다. 주어지는 값은 모두 정수이다.

• 첫째 줄에 장소의 개수 $n$이 주어진다. ($1 \le n \le 1000$)
• 다음 줄에 일행이 처음 있던 장소 $i$, 일행의 사람 수 $g$, 좀비가 되기까지 걸리는 시간 $s$가 주어진다. ($1 \le i \le n$, $1 \le g \le 100$, $1 \le s \le 100$)
  • 시각 $s$에 병원에 도착한 사람도 좀비가 되기 전에 병원을 찾은 것이다.
• 다음 줄에 병원의 개수 $m$이 주어진다. ($1 \le m \le n$)
• 이어지는 $m$개의 줄에 병원이 있는 장소 번호 $x$가 한 줄에 하나씩 주어진다. ($1 \le x \le n$)
• 다음 줄에 도로의 개수 $r$이 주어진다. ($0 \le r \le 1000$)
• 이어지는 $r$개의 줄에 도로 정보 $a$, $b$, $p$, $t$가 주어진다. ($1 \le a, b \le n$, $a \ne b$, $1 \le p \le 100$, $1 \le t \le 100$) 이 도로는 $a$에서 $b$로 가는 도로이고, 매 단위 시간마다 최대 $p$명이 이 도로에 들어설 수 있으며, 끝까지 지나가는 데 단위 시간 $t$가 걸린다.

일행은 시각 $0$에 장소 $i$에 있다. 도로에 들어서는 시각은 정수이고, 시각 $\tau$에 도로에 들어선 사람은 시각 $\tau + t$에 반대편 장소에 도착한다.

같은 장소 쌍 사이에 도로는 최대 2개, 곧 방향마다 하나씩 있다. 각 장소는 충분히 안전해서 얼마든지 가만히 서서 기다려도 되고, 한 장소에 있을 수 있는 사람 수에도 제한이 없다.

각 테스트 케이스마다 감염되지 않고 병원에 도달하는 최대 사람 수를 한 줄에 하나씩 출력한다.