#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 60;

int mod = 1000000007;

ll dp[100][2];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    ll X; cin >> X;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<ll> x(N);
    for(int i = N-1; i >= 0; i--){
        x[i] = X/A[i];
        X %= A[i];
    }

    dp[0][0] = 1;
    for(int i = 0; i < N; i++){
        ll kuri = (i == N-1) ? LLINF : A[i+1]/A[i];
        for(int j = 0; j <= 1; j++){
            if((x[i]+j) % kuri == 0){
                //y == 0 <=> z == 0
                int nj = (x[i]+j)/kuri;
                dp[i+1][nj] += dp[i][j];
            }
            else{
                dp[i+1][0] += dp[i][j];
                dp[i+1][1] += dp[i][j];
            }
        }
    }
    
    cout << dp[N][0] << endl;
    return 0;
}

/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */
#include <bits/stdc++.h>
using namespace std;

const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

using ld=long double;
const ld PI = acos((ld)-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) ld d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<ld, ld>;
using vd= vector<ld>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"

int isqrt(int i) {
    return (int)sqrt(i);
}

/* Its some kind of dijkstra.
 * But we cannot iterate all possible waiting times on all edges :/
 * But, the earliest time to pass an edge seems to be sqrt(D[i])
 * after begin, so it never makes sense to wait longer.
 * So we need to iterate only that edges where t is smaller
 * than sqrt(D[i]).
 *
 * How to get rid of TLE?
 */
const int INF=1e18;
void solve() {
    cini(n);
    cini(m);

    vector<vector<pii>> adj(n);
    vi C(m);
    vi D(m);
    for(int i=0; i<m; i++) {
        cini(a); a--;
        cini(b); b--;
        adj[a].emplace_back(b,i);
        adj[b].emplace_back(a,i);
        cin>>C[i];
        cin>>D[i];
    }

    vi dp(n, INF);          /* dp[i]=min time possible arriving at vertex i */
    priority_queue<pii> q;  /* <-mintime,vertex> */
    q.emplace(0, 0);
    dp[0]=0;
    while(q.size()) {
        auto [t,v]=q.top();
        q.pop();
        if(-t!=dp[v])
            continue;

        for(pii chl : adj[v]) {
            /* without waiting */
            int mii=dp[v]+C[chl.second]+D[chl.second]/(dp[v]+1);

            int optWait=max(dp[v], isqrt(D[chl.second])-1);
            mii=min(mii, optWait+C[chl.second]+D[chl.second]/(optWait+1));
            optWait++;
            mii=min(mii, optWait+C[chl.second]+D[chl.second]/(optWait+1));

            if(mii<dp[chl.first]) {
                dp[chl.first]=mii;
                q.emplace(-mii, chl.first);
            }
        }
    }

    if(dp[n-1]==INF)
        dp[n-1]=-1;
    cout<<dp[n-1]<<endl;
}

signed main() {
    solve();
}