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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)
template<class T, class U> void umin(T& x, const U& y){ x = min(x, (T)y);}
template<class T, class U> void umax(T& x, const U& y){ x = max(x, (T)y);}
template<class T, class U> void init(vector<T> &v, U x, size_t n) { v=vector<T>(n, (T)x); }
template<class T, class U, typename... W> void init(vector<T> &v, U x, size_t n, W... m) { v=vector<T>(n);  for(auto& a : v) init(a, x, m...); }
int n;
vector<ll> a, b;
map<pair<ll, int>, ll> H;
ll cc(ll x, ll q){
    if (x>=0) return (x+q-1)/q;
    else return x/q;
}
ll ff(ll x, ll q){
    if (x>=0) return x/q;
    else return (x-q+1)/q;
}
ll solve(ll x, int i){
    auto key = make_pair(x, i);
    if (H.count(key))
        return H[key];

    if (abs(x) > b[i])
        return 0;
    if (i==0)
        return abs(x) <= b[0];
    ll ret = 0;
    ret += solve(x, i-1);
    //-b[i-1] <= x + q * a[i] <= b[i-1]
    ll q1 = cc(-b[i - 1] - x, a[i]);
    ll q2 = ff(b[i - 1] - x, a[i]);
    ll lim = 1e18;
    if (i+1 < n)
        lim = a[i+1] / a[i];
    if (q1 == q2 && abs(q1) < lim && q1)
        ret += solve(x + q1 * a[i], i - 1);
    else if (q1 < q2) {
        if (q1 && abs(q1) < lim)
            ret += solve(x + q1 * a[i], i - 1);
        if (q2 && abs(q2) < lim)
            ret += solve(x + q2 * a[i], i - 1);
    }
//    cout << x << " " << i << " " << ret << endl;
    return H[key] = ret;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    ll x;
    cin >> n >> x;
    a.resize(n); b.resize(n);
    FOR(i, n) cin >> a[i];
    FOR(i, n-1) b[i] = a[i+1]-1;
    b[n-1] = 1e18;
    cout << solve(x, n-1) << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef WA_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

using ll  = long long;
using ull = unsigned long long;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=int(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=int(a);i>=(int)(b);i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod  = 1e9+7;
const int inf  = 0x3f3f3f3f;
const int maxn = 1e5+10;
struct edge {
    int to;
    ll c,d;
};
int main() {
#ifndef WA_DEBUG
    ios::sync_with_stdio(false);cin.tie(nullptr);
#endif
    int n,m;
    cin>>n>>m;
    vector<vector<edge>> g(n+1);
    rep(i,1,m) {
        int a,b;
        ll c,d;
        cin>>a>>b>>c>>d;
        g[a].pb({b,c,d});
        g[b].pb({a,c,d});
    }
    auto gett=[&](ll x) {
        if(x==0) return 1ll;
        ll tmp=sqrt(x);
        while(tmp*(tmp+1)<=x) tmp++;
        return tmp;
    };
    vector<ll> dis(n+1,ll(1e18));
    dis[1]=0;
    priority_queue<pair<ll,int>> q;
    q.push({0,1});
    while(!q.empty()) {
        auto now=q.top();q.pop();
        now.fi=-now.fi;
        if(now.fi!=dis[now.se]) continue;
        for(auto x:g[now.se]) {
            ll t=gett(x.d),val;
            if(now.fi+1<t) val=t-1+x.c+x.d/t;
            else val=now.fi+x.c+x.d/(now.fi+1);
            if(dis[x.to]>val) {
                dis[x.to]=val;
                q.push({-val,x.to});
            }
        }
    }
    if(dis[n]>9e17) cout<<-1<<'\n';
    else cout<<dis[n]<<'\n';
    return 0;
}
