There are N cities numbered 1 to N, connected by M railroads.

You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.

The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes. You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin. The transaction takes D_i minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.

For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Constraints

* 2 \leq N \leq 50
* N-1 \leq M \leq 100
* 0 \leq S \leq 10^9
* 1 \leq A_i \leq 50
* 1 \leq B_i,C_i,D_i \leq 10^9
* 1 \leq U_i < V_i \leq N
* There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).
* Each city t=2,...,N can be reached from City 1 with some number of railroads.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N


Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

Examples

Input

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Output

2
14


Input

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4


Output

5
5
7


Input

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1


Output

1
9003
14606
16510
16576


Input

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7


Output

1
3
5


Input

2 1 0
1 2 1 1
1 1000000000
1 1


Output

1000000001
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
struct P{
	int to,next;
	ll cost,tak;
}e[2600];
int tot = 0,n,m;
long long s;
ll c[60],t[60];
int head[100];

void add( int u,int v,long long a,long long  b)
{
	e[tot].cost = a;
	e[tot].tak = b;
	e[tot].to = v;
	e[tot].next = head[u];
	head[u] = tot++; 
}
long long dis[60][2600];
void dij(int x,ll y)
{
	queue<pair<int,ll> > q;
    q.push({1,s});
    for(int i = 1; i <= n;i++)
     for (int j = 0;j <= 2500;j++)
       {
       	dis[i][j]=0x3f3f3f3f3f3f3f3f;
	   }
	dis[1][s]=0;
	while(!q.empty())
	{
		int p1 = q.front().first;
	    ll p2 = q.front().second;
	    q.pop();
		for(int i = head[p1];i!=-1;i=e[i].next)
	    {// 
	    	if(p2>=e[i].cost && dis[e[i].to][p2-e[i].cost]>dis[p1][p2]+e[i].tak)
	    	  {
			  dis[e[i].to][p2-e[i].cost]=dis[p1][p2]+e[i].tak;
	          q.push({e[i].to,p2-e[i].cost});
			  }
		}
		if(dis[p1][min(ll(2500),p2+c[p1])] > dis[p1][p2]+t[p1])
		  {
		  	dis[p1][min((ll)2500,p2+c[p1])] = dis[p1][p2]+t[p1];
		  	q.push({p1,min((ll)2500,p2+c[p1])});
		  }
	}   
}
int main(){
	cin>>n>>m>>s;
	s = min(s,(ll)2500);
	for(int i = 1;i <= n;i++)
	 head[i]= -1;
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		ll a,b;
		scanf("%d%d%lld%lld",&u,&v,&a,&b);
        add(u,v,a,b);
        add(v,u,a,b);
	}
	for(int i = 1;i <= n;i++)
	 {
	 	scanf("%d%d",&c[i],&t[i]);
	 }
	dij(1,s);
	for(int i =2 ;i<= n;i++)
	 {
	 	long long ans = 0x3f3f3f3f3f3f3f3f;
	  for(int j = 0;j <=2500;j++)
	    ans = min(ans,dis[i][j]);
	  cout<<ans<<endl;
}
	return 0;
}