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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.OptionalLong;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class Main {
    public static void main(final String[] args) {
        final FastScanner scanner = new FastScanner(System.in);
        final int n = scanner.nextInt();
        final int m = scanner.nextInt();
        final int s = scanner.nextInt();

        final Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int i = 0; i < m; i++) {
            final int u = scanner.nextInt();
            final int v = scanner.nextInt();
            final int a = scanner.nextInt();
            final int b = scanner.nextInt();

            graph.computeIfAbsent(u, value -> new ArrayList<>()).add(new Edge(v, a, b));
            graph.computeIfAbsent(v, value -> new ArrayList<>()).add(new Edge(u, a, b));
        }

        final City[] cities = new City[n + 1];
        for (int i = 1; i <= n; i++) {
            final int c = scanner.nextInt();
            final int d = scanner.nextInt();
            cities[i] = new City(c, d);
        }

        final long[][] answers = new long[n + 1][2501];
        for (final long[] array : answers) {
            Arrays.fill(array, Long.MAX_VALUE);
        }
        final PriorityQueue<State> queue = new PriorityQueue<>(Comparator.comparingLong(state -> state.time));

        int index;
        for (index = 0; s + cities[1].rate * index < 2500; index++) {
            final int currentMoney = (int) (s + cities[1].rate * index);
            final long currentTime = cities[1].time * index;
            answers[1][currentMoney] = currentTime;
            for (final Edge next : graph.get(1)) {
                if (currentMoney >= next.cost) {
                    queue.add(new State(next.to, currentMoney - next.cost, currentTime + next.time));
                }
            }
        }
        answers[1][2500] = cities[1].time * index;
        for (final Edge next : graph.get(1)) {
            queue.add(new State(next.to, 2500 - next.cost, cities[1].time * index + next.time));
        }

        final Set<Integer> set = new HashSet<>();
        set.add(1);
        while (!queue.isEmpty()) {
            final State state = queue.poll();
            if (state.money < 0 || state.time >= answers[state.position][state.money]) {
                continue;
            }

            final List<Edge> nextList = graph.get(state.position);
            boolean flag = true;
            for (index = 0; state.money + cities[state.position].rate * index < 2500; index++) {
                final int currentMoney = (int) (state.money + cities[state.position].rate * index);
                final long currentTime = state.time + cities[state.position].time * index;
                if (currentTime >= answers[state.position][currentMoney]) {
                    flag = false;
                    break;
                }

                answers[state.position][currentMoney] = currentTime;
                for (final Edge next : nextList) {
                    queue.add(new State(next.to, currentMoney - next.cost, currentTime + next.time));
                }
            }
            if (flag && state.time + cities[state.position].time * index < answers[state.position][2500]) {
                answers[state.position][2500] = state.time + cities[state.position].time * index;
                for (final Edge next : nextList) {
                    queue.add(new State(next.to, 2500 - next.cost, answers[state.position][2500] + next.time));
                }
            }

            set.add(state.position);
            if (set.size() == n) {
                break;
            }
        }

        IntStream.rangeClosed(2, n)
                .mapToObj(i -> Arrays.stream(answers[i]))
                .map(LongStream::min)
                .map(OptionalLong::orElseThrow)
                .forEach(System.out::println);
    }

    private static class State {
        final int position;
        final int money;
        final long time;

        State(final int position, final int money, final long time) {
            this.position = position;
            this.money = money;
            this.time = time;
        }
    }

    private static class Edge {
        final int to;
        final int cost;
        final long time;

        Edge(final int to, final int cost, final long time) {
            this.to = to;
            this.cost = cost;
            this.time = time;
        }
    }

    private static class City {
        final long rate;
        final long time;

        City(final long rate, final long time) {
            this.rate = rate;
            this.time = time;
        }
    }

    private static class FastScanner {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(final InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}
    