#include <bits/stdc++.h>
using namespace std;

const int N = 55;
bool friendly[N];
int dp[N][1005];
queue <pair<int, int>> q;
bool in_q[N][1005];
int n;
const int INF = N*100;

struct edge{
    int y, T, W;
};

vector <edge> v[N];

int isEnough(int k){
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= k;j++){
            dp[i][j] = INF;
        }
    }
    dp[1][k] = 0;
    q.push({1, k});
    while(q.empty() == false){
        int node, w;
        node = q.front().first;
        w = q.front().second;
        q.pop();
        in_q[node][w] = 0;
        if(friendly[node]){
            dp[node][k] = dp[node][w];
            w = k;
        }
        for(auto it : v[node]){
            if(w >= it.W && dp[node][w] + it.T < dp[it.y][w - it.W]){
                dp[it.y][w - it.W] = dp[node][w] + it.T;
                if(in_q[it.y][w - it.W] == 0){
                    in_q[it.y][w - it.W] = 1;
                    q.push({it.y, w - it.W});
                }
            }
        }
    }
    int sol = INF;
    for(int i = 0;i <= k;i++){
        sol = min(sol, dp[n][i]);
    }
    return (sol == INF ? 0 : sol);
}

int main(){
    ifstream fin("lanterna.in");
    ofstream fout("lanterna.out");
    int k,m,i;
    fin>>n>>k;
    for(i = 1;i <= n;i++){
        fin>>friendly[i];
    }
    fin>>m;
    for(i = 1;i <= m;i++){
        edge t;
        int x,y;
        fin>>x>>y>>t.T>>t.W;
        t.y = y;
        v[x].push_back(t);
        t.y = x;
        v[y].push_back(t);
    }
    int lf, rg, md, sol;
    lf = 1;
    rg = k;
    sol = k;
    int tmin = isEnough(k);
    while(lf <= rg){
        md = (lf + rg)/2;
        int cmin = isEnough(md);
        if(cmin == tmin){
            sol = min(sol, md);
            rg = md - 1;
        }else{
            lf = md + 1;
        }
    }
    fout<<tmin<<' '<<sol;
    return 0;
}