#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>

using namespace std;
typedef long long ll;

int __gcd(int x, int y)
{
    if (y == 0) return x;
    return __gcd(y, x % y);
}


int main(){
    int n, m;
    int k = 0;
    ll s;
    int u, v;
    int a, b;
    vector<int> saisoku;
    pair<int, int> eki[51];
    vector<int> order;
    pair<int, int> uv[101][101];
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            uv[i][j].first = 0;
            uv[i][j].second = 0;
        }
    }
    cin >> n >> m >> s;
    order[0] = 0;
    for (int i = 1; i <= n; i++) {
        order[i] = i; 
    }
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        cin >> uv[u][v].first;
        cin >> uv[u][v].second;
    }
    for (int i = 1; i <= n; i++) {
        cin >> eki[i].first;
        cin >> eki[i].second;
    }
    do {
        int jikan = 0;
        ll okane = s;
        for (int i = 1; i <= n - 1; i++) {
            if (uv[order[i]][order[i+1]].first == 0) {
                break;
            }
            while (okane <uv[order[i]][order[i+1]].first) {
                okane += eki[order[i]].first;
                jikan += eki[order[i]].second;
            }
            jikan += uv[order[i]][order[i+1]].second;
            okane -= uv[order[i]][order[i+1]].first;
        }
        saisoku[k++] = jikan;
    } while (next_permutation(order.begin() + 2, order.end()));
    sort(saisoku.begin(), saisoku.end());
    for (int i = 0; i < k; i++) {
        cout << saisoku[i] << endl;
    }
    return 0;
}