Problem: Problem Statement

You are now participating in the Summer Training Camp for Programming Contests with your friend Jiro, who is an enthusiast of the ramen chain SIRO. Since every SIRO restaurant has its own tasteful ramen, he wants to try them at as many different restaurants as possible in the night. He doesn't have plenty of time tonight, however, because he has to get up early in the morning tomorrow to join a training session. So he asked you to find the maximum number of different restaurants to which he would be able to go to eat ramen in the limited time.

There are $n$ railway stations in the city, which are numbered $1$ through $n$. The station $s$ is the nearest to the camp venue. $m$ pairs of stations are directly connected by the railway: you can move between the stations $a_i$ and $b_i$ in $c_i$ minutes in the both directions. Among the stations, there are $l$ stations where a SIRO restaurant is located nearby. There is at most one SIRO restaurant around each of the stations, and there are no restaurants near the station $s$. It takes $e_i$ minutes for Jiro to eat ramen at the restaurant near the station $j_i$.

It takes only a negligibly short time to go back and forth between a station and its nearby SIRO restaurant. You can also assume that Jiro doesn't have to wait for the ramen to be served in the restaurants.

Jiro is now at the station $s$ and have to come back to the station in $t$ minutes. How many different SIRO's can he taste?

Input

The input is a sequence of datasets. The number of the datasets does not exceed $100$. Each dataset is formatted as follows:

> $n$ $m$ $l$ $s$ $t$
> $a_1$ $b_1$ $c_1$
> :
> :
> $a_m$ $b_m$ $c_m$
> $j_1$ $e_1$
> :
> :
> $j_l$ $e_l$

The first line of each dataset contains five integers:

* $n$ for the number of stations,

* $m$ for the number of directly connected pairs of stations,

* $l$ for the number of SIRO restaurants,

* $s$ for the starting-point station, and

* $t$ for the time limit for Jiro.




Each of the following $m$ lines contains three integers:

* $a_i$ and $b_i$ for the connected stations, and

* $c_i$ for the time it takes to move between the two stations.




Each of the following $l$ lines contains two integers:

* $j_i$ for the station where a SIRO restaurant is located, and

* $e_i$ for the time it takes for Jiro to eat at the restaurant.




The end of the input is indicated by a line with five zeros, which is not included in the datasets.

The datasets satisfy the following constraints:

* $2 \le n \le 300$

* $1 \le m \le 5{,}000$

* $1 \le l \le 16$

* $1 \le s \le n$

* $1 \le t \le 100{,}000$

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

* $1 \le c_i \le 1{,}000$

* $1 \le j_i \le n$

* $1 \le e_i \le 15$

* $s \ne j_i$

* $j_i$'s are 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 any $i \ne j$




Note that there may be some stations not reachable from the starting point $s$.

Output

For each data set, output the maximum number of different restaurants where Jiro can go within the time limit.

Sample Input


2 1 1 1 10
1 2 3
2 4
2 1 1 1 9
1 2 3
2 4
4 2 2 4 50
1 2 5
3 4 5
2 15
3 15
4 6 3 1 29
1 2 20
3 2 10
4 1 5
3 1 5
2 4 3
3 4 4
2 1
4 5
3 3
0 0 0 0 0

Output for the Sample Input


1
0
1
3





Example

Input

2 1 1 1 10
1 2 3
2 4
2 1 1 1 9
1 2 3
2 4
4 2 2 4 50
1 2 5
3 4 5
2 15
3 15
4 6 3 1 29
1 2 20
3 2 10
4 1 5
3 1 5
2 4 3
3 4 4
2 1
4 5
3 3
0 0 0 0 0


Output

1
0
1
3

Solution (in CPP):

Solution:
//Name: SIRO Challenge
//Level: 3
//Category: グラフ,Graph,縮約,巡回セールスマン問題,TSP,練習問題
//Note:

/**
 * 問題となるのはいくつの店を回ったかであるから、あるパターンで店が訪問済みになる最短時間を覚えておけば良い。
 * これは巡回セールスマン問題のようにすればできる。
 * ただし、与えられたグラフに対してそのまま訪問済みの店集合を持たせるように拡張すると、頂点数が多くなりすぎるため、先に縮約しておく。
 * 縮約は、全点対最短距離を求めておき、スタートと店だけからなるグラフに再構成すればよい（Dijkstra法などを使えばもっと速くなる）。
 *
 * グラフが連結とは限らないことに注意。
 *
 * オーダーは O(N^3 + L^2 2^L)。
 */

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <unordered_map>

using namespace std;

bool solve() {
    int N, M, L, S, T;
    if(!(cin >> N >> M >> L >> S >> T)) return false;
    if(!N && !M && !L && !S && !T) return false;
    --S;

    vector<vector<int>> org_g(N, vector<int>(N, -1));
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        org_g[a][b] = org_g[b][a] = c;
    }
    for(int i = 0; i < N; ++i) {
        org_g[i][i] = 0;
    }
    for(int k = 0; k < N; ++k) {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                if(org_g[i][k] == -1 || org_g[k][j] == -1) continue;
                const int nl = org_g[i][k] + org_g[k][j];
                if(org_g[i][j] == -1 || org_g[i][j] > nl) {
                    org_g[i][j] = nl;
                }
            }
        }
    }

    // グラフを再構築する。
    unordered_map<int,int> dict;
    dict[0] = S;
    vector<vector<int>> graph(L+1, vector<int>(L+1, -1));
    vector<int> es(L+1, 0);
    for(int i = 1; i <= L; ++i) {
        int j;
        cin >> j >> es[i];
        --j;
        for(const auto &p : dict) {
            graph[p.first][i] = graph[i][p.first] = org_g[p.second][j];
        }
        dict[i] = j;
    }
    for(int i = 0; i <= L; ++i) {
        graph[i][i] = 0;
    }

    // TSP
    vector<vector<int>> dp(1<<(L+1), vector<int>(L+1, -1));
    dp[0][0] = 0;
    for(int pat = 0; pat < (1<<(L+1)); ++pat) {
        for(int i = 0; i <= L; ++i) {
            if(dp[pat][i] == -1) continue;
            for(int j = 0; j <= L; ++j) {
                if(graph[i][j] == -1) continue;
                const int nt = dp[pat][i] + graph[i][j] + es[j];
                const int np = pat | (1<<j);
                if(nt <= T && (dp[np][j] == -1 || dp[np][j] > nt)) {
                    dp[np][j] = nt;
                }
            }
        }
    }

    int ans = 0;
    for(int pat = 0; pat < (1<<(L+1)); ++pat) {
        if(dp[pat][0] != -1) {
            ans = max(ans, __builtin_popcount(pat & ~1));
        }
    }
    cout << ans << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}