#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=1005;

ll E[MX][MX], F[MX][MX];
vector<array<ll,3>> G[MX];
vector<ll> T;
vector<pair<ll,ll>> v;
vector<int> W, S;
int L,N,X,M;

ll mx;

pair<ll,ll> work(ll Y, int id) {
        ll cur=Y;
        ll res=-1;
        for(int j=1;j<M;j++) {
                array<ll,3> t={cur,0,0};
                auto nxt=lower_bound(G[j].begin(),G[j].end(),t);
                if(nxt!=G[j].begin()) {
                        nxt--;
                        cur+=1LL*(S[j]-S[j-1])*X;
                        if(cur<(*nxt)[1]) {
                                cur=(*nxt)[1];
                                if(res==-1) res=(*nxt)[2];
                        }
                } else {
                        cur+=1LL*(S[j]-S[j-1])*X;
                }
        }

        if(res==-1) {
                return {-1,-1};
        } 
        return {res,cur};
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
        W.push_back(X);
        ::T=T, ::W=W, ::S=S;
        ::L=L, ::N=N, ::X=X, ::M=M;

        for(int i=0;i<N;i++) {
                F[0][i]=T[i];
        }

        for(int j=1;j<M;j++) {
                for(int i=0;i<N;i++) {
                        E[j][i]=F[j-1][i]+1LL*W[i]*(S[j]-S[j-1]);
                }

                vector<int> ord;
                for(int i=0;i<N;i++) ord.push_back(i);

                sort(ord.begin(),ord.end(),[&](int x, int y){
                        return F[j-1][x]<F[j-1][y];
                });

                ll mx=0;
                for(int p=0;p<ord.size();p++) {
                        int q=p;
                        while(q+1<ord.size() && F[j-1][ord[q+1]]==F[j-1][ord[q]]) q++;
                        for(int k=p;k<=q;k++) {
                                F[j][ord[k]]=max(mx,E[j][ord[k]]);
                        }
                        for(int k=p;k<=q;k++) {
                                mx=max(mx,E[j][ord[k]]);
                        }
                        G[j].push_back({F[j-1][ord[p]],mx,ord[p]});
                        p=q;       
                }
        }

        mx=*max_element(F[M-1],F[M-1]+N);

        ll prv=0;
        while(v.size()<=2*N) {
                ll l=prv,r=mx,res=-1;
                while(l<=r) {
                        ll mid=(l+r)/2;
                        if(work(mid,v.size()+1).first==work(prv,v.size()+1).first) {
                                l=mid+1,res=mid;
                        } else {
                                r=mid-1;
                        }
                }
                v.push_back(work(prv,v.size()+1));
                v.back().first=prv;
                if(res==-1) break;
                prv=res+1;
        }

        return;
}

long long arrival_time(long long Y) {
        auto it=upper_bound(v.begin(),v.end(),make_pair(Y,0ll));

        if(it==v.end()) return 1LL*X*L+Y;

        it--;
        if((*it).second==-1) {
                return 1LL*X*L+Y;
        } else {
                return (*it).second;
        }
}