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:
#include <cassert>// c
#include <iostream>// io
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>// container
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <algorithm>// other
#include <complex>
#include <numeric>
#include <functional>
#include <random>
#include <regex>
using namespace std;

typedef long long ll;

#define ALL(c) (begin(c)),(end(c))
#define REP(i,n) FOR(i,0,n)
#define REPr(i,n) FORr(i,0,n)
#define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define FORr(i,l,r) for(int i=(int)(r)-1;i>=(int)(l);--i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end())
//debug
#define DUMP(x)  cerr << #x << " = " << (x)
#define LINE()    cerr<< " (L" << __LINE__ << ")"

class range {
private:
	struct Iter{
		int v;
		int operator*(){return v;}
		bool operator!=(Iter& itr) {return v < itr.v;}
		void operator++() {++v;}
	};
	Iter i, n;
public:
	range(int n) : i({0}), n({n}) {}
	range(int i, int n) : i({i}), n({n}) {}
	Iter& begin() {return i;}
	Iter& end() {return n;}
};

//output
template<typename T> ostream& operator << (ostream& os, const vector<T>& as){REP(i,as.size()){if(i!=0)os<<" "; os<<as[i];}return os;}
template<typename T> ostream& operator << (ostream& os, const vector<vector<T>>& as){REP(i,as.size()){if(i!=0)os<<endl; os<<as[i];}return os;}
template<typename T> ostream& operator << (ostream& os, const set<T>& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os<<a;}return os;}
template<typename T1,typename T2> ostream& operator << (ostream& os, const pair<T1,T2>& p){os<<p.first<<" "<<p.second;return os;}
template<typename K,typename V> ostream& operator << (ostream& os, const map<K,V>& m){bool isF=true;for(auto& p:m){if(!isF)os<<endl;os<<p;isF=false;}return os;}
template<typename T1> ostream& operator << (ostream& os, const tuple<T1>& t){os << get<0>(t);return os;}
template<typename T1,typename T2> ostream& operator << (ostream& os, const tuple<T1,T2>& t){os << get<0>(t)<<" "<<get<1>(t);return os;}
template<typename T1,typename T2,typename T3> ostream& operator << (ostream& os, const tuple<T1,T2,T3>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4,T5>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t)<<" "<<get<4>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4,T5,T6>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t)<<" "<<get<4>(t)<<" "<<get<5>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4,T5,T6,T7>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t)<<" "<<get<4>(t)<<" "<<get<5>(t)<<" "<<get<6>(t);return os;}

//input
char tmp[1000];
#define nextInt(n) scanf("%d",&n)
#define nextLong(n) scanf("%lld",&n) //I64d
#define nextDouble(n) scanf("%lf",&n) 
#define nextChar(n) scanf("%c",&n)
#define nextString(n) scanf("%s",tmp);n=tmp

// values
template<typename T> T INF(){assert(false);};
template<> int INF<int>(){return 1<<28;};
template<> ll INF<ll>(){return 1LL<<58;};
template<> double INF<double>(){return 1e16;};

template<class T> T EPS(){assert(false);};
template<> int EPS<int>(){return 1;};
template<> ll EPS<ll>(){return 1LL;};
template<> double EPS<double>(){return 1e-8;};
template<> long double EPS<long double>(){return 1e-8;};


template<typename T,typename U> T pmod(T v,U M){return (v%M+M)%M;}


typedef int Cost; Cost CINF=1<<28;
struct Edge{
	int f,t;Cost c;
	Edge(int f,int t,Cost c) : f(f),t(t),c(c) {};
	bool operator<(Edge r) const{return c<r.c;}
	bool operator>(Edge r) const{return c>r.c;}
};
typedef vector<vector<Edge> >  Graph;

struct Task{
    int prev,pos;Cost c;
    Task(int prev,int pos,Cost c)
        :prev(prev),pos(pos),c(c){};
    bool operator>(const Task& r) const{ return c > r.c;}
};
vector<Cost> dijkstra(const Graph& g,const int s,vector<int>& prev){
    const int V=g.size();
    vector<Cost> d(V,CINF);d[s]=0;
    fill(ALL(prev), -2);
    
    priority_queue<Task,vector<Task>,greater<Task> > que;que.push(Task(-1,s,0));// [ ,e,,f, ] <=> e.cost < e.cost
    vector<bool> visited(V);
    while(!que.empty()){
        Task task=que.top();que.pop();
        if(visited[task.pos])continue;
        visited[task.pos]=true;
        prev[task.pos]=task.prev;
        EACH(e,g[task.pos])if(d[e->t]>d[e->f]+e->c){
            d[e->t]=d[e->f]+e->c;
            que.push(Task(e->f,e->t,d[e->t]));
        }   
    }
    return d;
}
vector<Cost> dijkstra(const Graph& g,const int s){
    vector<int> prev(g.size());return dijkstra(g,s,prev);
}

class Main{
	public:

	void run(){

		while(true){
			int n,m,l,s,t;cin >> n >> m >> l >> s >> t;if(n==0)break;
			s--;
			Graph g(n);
			REP(i,m){
				int a,b,c;cin >> a >> b >> c;a--;b--;
				g[a].push_back(Edge(a,b,c));
				g[b].push_back(Edge(b,a,c));
			}

			js.clear();
			REP(i,l){
				int v,e;cin >> v >> e;v--;
				js[v]=e;
			}

			enc.clear();EACH(it,js)enc[it->first]=0;enc[s]=0;
			N=0;EACH(it,enc)enc[it->first]=N++;
			dec.clear();EACH(it,enc)dec[it->second]=it->first;

			ds = vector<vector<int>> (N,vector<int>(N));
			EACH(it,dec){
				vector<int> d=dijkstra(g,it->second);
				EACH(itj,dec)ds[it->first][itj->first]=d[itj->second];
			}
				
			dp =vector<vector<int>>(N,vector<int>(1<<N,INF<int>()));
			dp[enc[s]][0]=0;
			REP(i,N)REP(bit,1<<N)rec(i,bit);

			int Mv=0;
			REP(i,N)REP(bit,1<<N)if(dp[i][bit]+ds[i][enc[s]]<=t){
				int bc=0;REP(k,N)if(bit&(1<<k))bc++;
				Mv=max(Mv,bc);
			}
			cout << Mv <<endl;
		}
	}
	
	map<int,int> js;
	map<int,int> enc;
	map<int,int> dec;
	vector<vector<int>> dp;
	vector<vector<int>> ds;
	int N;
	int rec(int i,int bit){
		if(dp[i][bit]!=INF<int>())return dp[i][bit];
		dp[i][bit]=INF<int>()-1;
		if(((bit>>i)&1) && js.count(dec[i])){
			REP(j,N)dp[i][bit]=min(dp[i][bit],rec(j,bit-(1<<i))+ds[j][i]+js[dec[i]]);
		}
		return dp[i][bit];
	}

};

int main(){
	cout <<fixed<<setprecision(20);
	cin.tie(0);
	ios::sync_with_stdio(false);
	Main().run();
	return 0;
}