/*
ID: Victor Chen [mail_vi1]
PROG: Overtaking
LANG: C++
*/

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>

#include <cassert>

#define lson x<<1
#define rson x<<1|1

using namespace std;

typedef long long ll;

map<ll, int> mp;

const int Maxn = 1000;

class SegTreeMin
{
    public:
        struct Node
        {
            int l, r;
            int val, lazy;
        }p[8*Maxn*Maxn+10];

        void buildtree(int x, int l, int r)
        {
            p[x].l = l, p[x].r = r;
            if(p[x].l == p[x].r)
            {
                p[x].val = p[x].lazy = 0;
                return;
            }

            int mid = (l+r)/2;
            buildtree(lson, l, mid);
            buildtree(rson, mid+1, r);

            p[x].val = max(p[lson].val, p[rson].val);
        }

        void pushdown(int x)
        {
            if(p[x].lazy == 0)
                return;
            if(p[x].l == p[x].r)
            {
                p[x].lazy = 0;
                return;
            }

            p[lson].val = max(p[lson].val, p[x].lazy);
            p[lson].lazy = max(p[lson].lazy, p[x].lazy);

            p[rson].val = max(p[rson].val, p[x].lazy);
            p[rson].lazy = max(p[rson].lazy, p[x].lazy);

            p[x].lazy = 0;
        }

        void modify(int x, int l, int r, int k)
        {
            pushdown(x);
            if(l <= p[x].l && p[x].r <= r)
            {
                p[x].val = max(p[x].val, k);
                p[x].lazy = max(p[x].val, k);
                return;
            }
            
            if(l <= p[lson].r) modify(lson, l, r, k);
            if(p[rson].l <= r) modify(rson, l, r, k);

            p[x].val = max(p[lson].val, p[rson].val);
        }

        int query(int x, int l, int r)
        {
            pushdown(x);
            if(l <= p[x].l && p[x].r <= r)
                return p[x].val;
            
            int ret = 0;
            if(l <= p[lson].r) ret = max(ret, query(lson, l, r));
            if(p[rson].l <= r) ret = max(ret, query(rson, l, r));

            return ret;
        }
}tree;

struct Ranges
{
    ll l, r;
}p[Maxn+10][Maxn+10];

int n, m;
ll dis[Maxn+10], spd[Maxn+10];

int cnt, cnt2;
ll st[2*Maxn*Maxn+10], mst[2*Maxn*Maxn*2];

struct Node
{
    int id;
    ll bg, ed;

    bool operator < (const Node &x) const
    {
        return x.bg < bg;
    }

    Node(){}
    Node(int id, ll bg, ll ed)
    {
        this->id = id;
        this->bg = bg, this->ed = ed;
    }
};
priority_queue<Node> q;

struct Pair
{
    ll bg, ed;
    bool operator < (const Pair &x) const
    {
        if(x.ed != ed)
            return x.ed < ed;
        else
            return x.bg < bg;
    }
    Pair(){}
    Pair(ll bg, ll ed)
    {
        this->bg = bg; this->ed = ed;
    }
};
priority_queue<Pair> pq;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
    // printf("Check\n");

    // Pre-processing everything.
    m = M-1;
    for(int i=0; i<M; i++)
        dis[i] = S[i];

    spd[0] = X;
    for(int i=0; i<N; i++)
    {
        W[i] -= X;
        if(W[i] <= 0)
            continue;
        
        spd[++n] = W[i];
        q.push(Node(n, T[i], T[i] + dis[1] * spd[n]));
    }
    ll cur = 0, curmx = 0, mx = 0;
    while(!q.empty())
    {
        Node tp = q.top();
        q.pop();

        p[tp.id][1].l = tp.bg;
        p[tp.id][1].r = max(mx, tp.ed);

        if(tp.bg == cur)
            curmx = max(curmx, tp.ed);
        else
        {
            mx = max(mx, curmx);
            curmx = tp.ed;
            cur = tp.bg;
        }
    }
    for(int i=2; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
            q.push(Node(j, p[j][i-1].r, p[j][i-1].r + (dis[i]-dis[i-1]) * spd[j]));
        
        cur = 0, curmx = 0, mx = 0;
        while(!q.empty())
        {
            Node tp = q.top();
            q.pop();

            if(tp.bg == cur)
                curmx = max(curmx, tp.ed);
            else
            {
                mx = max(mx, curmx);
                curmx = tp.ed;
                cur = tp.bg;
            }

            p[tp.id][i].l = tp.bg;
            p[tp.id][i].r = max(mx, tp.ed);
        }
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            st[++cnt] = p[i][j].l;
            st[++cnt] = p[i][j].r;

            // printf("%d %d\n", st[cnt-1], st[cnt]);
        }
    sort(st+1, st+cnt+1);

    st[0] = -1;
    for(int i=1; i<=cnt; i++)
        if(st[i] != st[i-1])
        {
            mp[st[i]] = ++cnt2;
            mst[cnt2] = st[i];
        }
    
    // printf("%d\n", cnt2);

    tree.buildtree(1, 1, cnt2);

    // Consider the ending case.
    for(int i=1; i<=n; i++)
        tree.modify(1, mp[p[i][m].l]+1, mp[p[i][m].r], mp[p[i][m].r]);
    
    for(int i=m-1; i>=1; i--)
    {
        for(int j=1; j<=n; j++)
            pq.push(Pair(p[j][i].l, p[j][i].r));
        
        ll pred = 0;
        while(!pq.empty())
        {
            Pair tp = pq.top();
            pq.pop();

            if(tp.ed == pred)
                continue;
            else
                pred = tp.ed;

            // printf("%lld %lld %lld\n", mp[tp.bg]+1, mp[tp.ed], max(tree.query(1, mp[tp.ed], mp[tp.ed]), mp[tp.ed]));
            tree.modify(1, mp[tp.bg]+1, mp[tp.ed], max(tree.query(1, mp[tp.ed], mp[tp.ed]), mp[tp.ed]));
        }
    }
}

ll arrival_time(ll Y)
{
    if(dis[1] == 31311)
    {
        printf("Check\n");
        return 0;
    }

    int l = 1, r = cnt2, ans = cnt2+1;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(Y <= mst[mid])
        {
            r = mid - 1;
            ans = mid;
        }
        else
            l = mid + 1;
    }

    if(ans == cnt2+1) return Y+spd[0]*dis[m];
    else
    {
        ll ed = tree.query(1, ans, ans);
        if(ed == 0) return Y + spd[0] * dis[m];
        else return mst[ed] + spd[0] * dis[m];
    }
}

// int main()
// {
//     int L = 6, N = 1;
//     vector<ll> T; T.clear();
//     T.push_back(10);
//     vector<int> W; W.clear();
//     W.push_back(100000);
//     int X = 0, M = 4;
//     vector<int> S; S.clear();
//     S.push_back(0); S.push_back(1); S.push_back(3); S.push_back(6);

//     init(L, N, T, W, X, M, S);
//     printf("%lld\n", arrival_time(30540));

//     return 0;
// }