SIRO Challenge

You and your friend Jiro are at a summer training camp for programming contests. Jiro is a devoted fan of the ramen chain SIRO. Every SIRO restaurant serves its own ramen, so he wants to eat at as many different restaurants as he can tonight. His time is short, because he has to get up early tomorrow for a training session. He asked you to find the largest number of different restaurants he can reach and eat at within the time he has.

The city has $n$ railway stations, numbered $1$ through $n$. Station $s$ is the closest one to the camp venue. $m$ pairs of stations are directly connected by railway: you move between station $a_i$ and station $b_i$ in $c_i$ minutes, in either direction. There is a SIRO restaurant near $l$ of the stations. At most one SIRO restaurant is near any single station, and no restaurant is near station $s$. Jiro takes $e_i$ minutes to eat ramen at the restaurant near station $j_i$.

Walking between a station and the restaurant near it takes a negligibly short time. Assume also that Jiro never waits for his ramen to be served.

Jiro is at station $s$ now and has to come back to that station within $t$ minutes. How many different SIRO restaurants can he taste?

The input is a sequence of datasets. The number of datasets does not exceed $100$. Each dataset has this format.

n m l s t
a1 b1 c1
:
:
am bm cm
j1 e1
:
:
jl el

The first line of each dataset holds five integers.

• $n$, the number of stations

• $m$, the number of directly connected pairs of stations

• $l$, the number of SIRO restaurants

• $s$, the starting station

• $t$, the time limit for Jiro

Each of the next $m$ lines holds three integers.

• $a_i$ and $b_i$, the two connected stations

• $c_i$, the time it takes to move between those two stations

Each of the next $l$ lines holds two integers.

• $j_i$, the station a SIRO restaurant is near

• $e_i$, the time Jiro takes to eat at that restaurant

The end of the input is a line with five zeros. That line is not a dataset.

Every dataset satisfies these constraints.

• $2 \le n \le 300$

• $1 \le m \le 5000$

• $1 \le l \le 16$

• $1 \le s \le n$

• $1 \le t \le 100000$

• $1 \le a_i, b_i \le n$

• $1 \le c_i \le 1000$

• $1 \le j_i \le n$

• $1 \le e_i \le 15$

• $s \ne j_i$

• The $j_i$ are all distinct.

• $a_i \ne b_i$

• $(a_i, b_i) \ne (a_j, b_j)$ and $(a_i, b_i) \ne (b_j, a_j)$ for every $i \ne j$

Some stations may be unreachable from the starting point $s$.

For each dataset, print on its own line the largest number of different restaurants Jiro can go to within the time limit.