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:
#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-5L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define seg_size 262144LL
#define MOD 998244353LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

// geometry library

typedef complex<long double> Point;
typedef pair<complex<long double>, complex<long double>> Line;

typedef struct Circle {
    complex<long double> center;
    long double r;
}Circle;

//内積、 dot(a,b) = |a||b|cos()
long double dot(Point a, Point b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}
//外積、cross(a,b) = |a||b|sin()
long double cross(Point a, Point b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

//線分と点の距離
long double Dist_Line_Point(Line a, Point b) {
    if (dot(a.second - a.first, b - a.first) < eps) return abs(b - a.first);
    if (dot(a.first - a.second, b - a.second) < eps) return abs(b - a.second);
    return abs(cross(a.second - a.first, b - a.first)) / abs(a.second - a.first);
}

//線分の交差判定
int is_intersected_ls(Line a, Line b) {
    return (cross(a.second - a.first, b.first - a.first) * cross(a.second - a.first, b.second - a.first) < 0) &&
        (cross(b.second - b.first, a.first - b.first) * cross(b.second - b.first, a.second - b.first) < 0);
}

//線分の交点
Point intersection_l(Line a, Line b) {
    Point da = a.second - a.first;
    Point db = b.second - b.first;
    return a.first + da * cross(db, b.first - a.first) / cross(db, da);
}

//線分と線分の距離
long double Dist_Line_Line(Line a, Line b) {
    if (is_intersected_ls(a, b) == 1) {
        return 0;
    }
    return min({ Dist_Line_Point(a,b.first), Dist_Line_Point(a,b.second),Dist_Line_Point(b,a.first),Dist_Line_Point(b,a.second) });
}

//円と円の交点
pair<Point, Point> intersection_Circle_Circle(Circle a, Circle b) {
    long double dist = abs(a.center - b.center);
    assert(dist <= eps + a.r + b.r);
    assert(dist+eps >= abs(a.r - b.r));
    Point target = b.center - a.center;
    long double pointer = target.real() * target.real() + target.imag() * target.imag();
    long double aa = pointer + a.r * a.r - b.r * b.r;
    aa /= 2.0L;
    Point l{ (aa * target.real() + target.imag() * sqrt(pointer * a.r * a.r - aa * aa))/pointer,
            (aa* target.imag() - target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer};
    Point r{ (aa * target.real() - target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,
        (aa * target.imag() + target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };
    r = r + a.center;
    l = l + a.center;
    return mp(l, r);
}

//end of geometry

template<typename A>
A pows(A val, ll b) {
    assert(b >= 1);
    A ans = val;
    b--;
    while (b) {
        if (b % 2) {
            ans *= val;
        }
        val *= val;
        b /= 2LL;
    }
    return ans;
}

template<typename A>
class Compressor {
public:
    bool is_zipped = false;
    map<A, ll> zipper;
    map<ll, A> unzipper;
    queue<A> fetcher;
    Compressor(){
        is_zipped = false;
        zipper.clear();
        unzipper.clear();
    }
    void add(A now) {
        assert(is_zipped == false);
        zipper[now] = 1;
        fetcher.push(now);
    }
    void exec() {
        assert(is_zipped == false);
        int cnt = 0;
        for (auto i = zipper.begin(); i != zipper.end(); ++i) {
            i->second = cnt;
            unzipper[cnt] = i->first;
            cnt++;
        }
        is_zipped = true;
    }
    ll fetch() {
        assert(is_zipped == true);
        A hoge = fetcher.front();
        fetcher.pop();
        return zipper[hoge];
    }
    ll zip(A now) {
        assert(is_zipped == true);
        assert(zipper.find(now) != zipper.end());
        return zipper[now];
    }
    A unzip(ll a) {
        assert(is_zipped == true);
        assert(a < unzipper.size());
        return unzipper[a];
    }
    ll next(A now) {
        auto x = zipper.upper_bound(now);
        if (x == zipper.end()) return zipper.size();
        return (ll)((*x).second);
    }
    ll back(A now) {
        auto x = zipper.lower_bound(now);
        if (x == zipper.begin()) return -1;
        x--;
        return (ll)((*x).second);
    }
};

template<typename A>
class Matrix {
public:
    vector<vector<A>> data;
    Matrix(vector<vector<A>> a) :data(a){

    }
    Matrix operator + (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = obj.data[i][q] + (this -> data[i][q]);
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator - (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = this->data[i][q] - obj.data[i][q];
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator * (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data[0].size());
        REP(i, this -> data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[0].size()) {
                A hoge = (this -> data[i][0]) * (obj.data[0][q]);
                for(int t = 1;t < obj.data[i].size();++t){
                    hoge += this -> data[i][t] * obj.data[t][q];
                }
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix &operator *= (const Matrix obj) {
        *this = (*this * obj);
        return *this;
    }
    Matrix& operator += (const Matrix obj) {
        *this = (*this + obj);
        return *this;
    }
    Matrix& operator -= (const Matrix obj) {
        *this = (*this - obj);
        return *this;
    }
};

class modint {
public:
    using u64 = std::uint_fast64_t;
    u64 value = 0;
    u64 mod;
    modint(ll a, ll b): value(((a%b) + 2 * b) % b),mod(b) {

    }
    modint operator+(const modint rhs) const{
        return modint(*this) += rhs;
    }
    modint operator-(const modint rhs) const{
        return modint(*this) -= rhs;
    }
    modint operator*(const modint rhs) const {
        return modint(*this) *= rhs;
    }
    modint operator/(const modint rhs) const{
        return modint(*this) /= rhs;
    }
    modint& operator+=(const modint rhs) {
        assert(rhs.mod == mod);
        value += rhs.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
    modint& operator-=(const modint rhs) {
        assert(rhs.mod == mod);
        if (value < rhs.value) {
            value += mod;
        }
        value -= rhs.value;
        return *this;
    }
    modint& operator*=(const modint rhs) {
        assert(rhs.mod == mod);
        value = (value *  rhs.value) % mod;
        return *this;
    }
    modint& operator/=(modint rhs) {
        assert(rhs.mod == mod);
        ll rem = mod - 2;
        while (rem) {
            if (rem % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            rem /= 2LL;
        }
        return *this;
    }
    friend ostream& operator<<(ostream& os, modint& p) {
        os << p.value;
        return (os);
    }
};

template<typename A,typename B>
class Dijkstra {
public:
    vector<vector<pair<int, A>>> vertexs;
    B Cost_Function;
    Dijkstra(int n, B cost) : Cost_Function(cost){
        vertexs = vector<vector<pair<int, A>>>(n, vector<pair<int, A>>{});
    }
    ~Dijkstra() {
        vertexs.clear();
    }
    void add_edge(int a, int b, A c) {
        vertexs[a].push_back(mp(b, c));
    }
    vector<ll> build_result(int StartPoint) {
        vector<ll> dist(vertexs.size(), 2e18);
        dist[StartPoint] = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> next;
        next.push(make_pair(0, StartPoint));
        while (next.empty() == false) {
            pair<ll, int> now = next.top();
            next.pop();
            if (dist[now.second] != now.first) continue;
            for (auto x : vertexs[now.second]) {
                ll now_cost = now.first + Cost_Function(x.second);
                if (dist[x.first] > now_cost) {
                    dist[x.first] = now_cost;
                    next.push(mp(now_cost, x.first));
                }
            }
        }
        return dist;
    }
};

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

#define int ll
int dp[17][(1 << 17)];
void solve(){
    while (true) {
        int n, m, l, s, t;
        cin >> n >> m >> l >> s >> t;
        if (n == 0) return;
        s--;
        auto coster = [](int a) {
            return a;
        };
        Dijkstra<int, decltype(coster)> graph(n, coster);
        REP(i, m) {
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            graph.add_edge(a, b, c);
            graph.add_edge(b, a, c);
        }
        vector<pair<int, int>> ramens;
        ramens.push_back(mp(s, 0));
        REP(i, l) {
            int a, b;
            cin >> a >> b;
            a--;
            ramens.push_back(mp(a, b));
        }
        l++;
        ll dist[18][18] = {};
        REP(i, l) {
            vector<int> hoge = graph.build_result(ramens[i].first);
            REP(q, hoge.size()) {
                REP(j, l) {
                    if (ramens[j].first == q) {
                        dist[i][j] = hoge[q];
                    }
                }
            }
        }
        REP(i, l) {
            REP(q, (1 << l)) {
                dp[i][q] = 2e18;
            }
        }
        dp[0][0] = 0;
        priority_queue<tuple<int, int, int>> next;
        next.push(make_tuple(0, 0, 0));
        int ans = 0;
        while (next.empty() == false) {
            tuple<int, int, int> now = next.top();
            next.pop();
            get<0>(now) *= -1;
            if (get<0>(now) > t) continue;
            if (dp[get<1>(now)][get<2>(now)] != get<0>(now)) continue;
            if (get<1>(now) == 0) {
                int cnt = 0;
                REP(q, l) {
                    if ((1 << q) & get<2>(now)) cnt++;
                }
                ans = max(ans, cnt - 1);
            }
            REP(q, l) {
                if (get<2>(now)& (1 << q)) continue;
                if(dist[get<1>(now)][q] + get<0>(now) + ramens[q].second <= t)
                if (dist[get<1>(now)][q] + get<0>(now) + ramens[q].second < dp[q][get<2>(now) + (1 << q)]) {
                    dp[q][get<2>(now) + (1 << q)] = dist[get<1>(now)][q] + get<0>(now) + ramens[q].second;
                    next.push(make_tuple(-dp[q][get<2>(now) + (1 << q)], q, get<2>(now) + (1 << q)));
                }
            }
        }
        cout << ans << endl;
    }
}

#undef int
int main() {
    init();
    solve();
}