#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <memory>
using namespace std;

const int INF = 1e9;

struct Edge {
    int to, cost, time;
    Edge(int t, int c, int tm) : to(t), cost(c), time(tm) {}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, C, V;
    cin >> N >> C, V;
    
    // Use unique_ptr for automatic memory management with move semantics
    auto input = make_unique<int[]>(4 * V);
    for (int i = 0; i < 4 * V; i++) {
        cin >> input[i];
    }
    
    // Build graph with move semantics
    vector<vector<Edge>> graph(N);
    for (int i = 0; i < V; i++) {
        int s = input[i] - 1;
        int t = input[V + i] - 1;
        int cost = input[2 * V + i];
        int time = input[3 * V + i];
        graph[s].emplace_back(t, cost, time);
    }
    
    // Free input memory early
    input.reset();
    
    // Use 2D array with unique_ptr for DP table
    auto dp = make_unique<int[]>(N * (C + 1));
    fill_n(dp.get(), N * (C + 1), INF);
    dp[0 * (C + 1) + C] = 0;
    
    // Main DP loop with pointer arithmetic
    for (int i = 0; i < N; i++) {
        int* current_row = dp.get() + i * (C + 1);
        auto& edges = graph[i];
        
        for (int k = C; k >= 0; k--) {
            if (current_row[k] == INF) continue;
            
            for (const auto& edge : edges) {
                if (k >= edge.cost) {
                    int* target_row = dp.get() + edge.to * (C + 1);
                    int& target = target_row[k - edge.cost];
                    int new_time = current_row[k] + edge.time;
                    if (new_time < target) {
                        target = new_time;
                    }
                }
            }
        }
    }
    
    // Calculate result with move of the last row
    int* last_row = dp.get() + (N - 1) * (C + 1);
    int result = INF;
    for (int k = 0; k <= C; k++) {
        result = min(result, last_row[k]);
    }
    
    cout << (result == INF ? -1 : result) << endl;
    
    return 0;
}