# include <bits/stdc++.h>
using namespace std;
int n,m,t,f,d;
const int diff = 15;
pair <int,int> stations[1005];
mt19937 Rand(156958);
const int MAX = 500;
const clock_t begin_time = clock();
const float Time = 4.0;
struct bus
{
    int len;
    vector <int> stat;
    vector <int> stat2;
    vector <int> statf;
    vector <int> clients;
    vector <int> times;
    vector <int> times2;
    vector <int> timesf;
    vector <pair <int,int>> swv;
    int curr,time;
    int L,R;
    int starttime;
    int whole;
};
long long BESTANS=1e18;
bus b[1005];
struct tourists
{
    int num,time,st;
};
tourists tour[1005];
void read()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++)
    {
        cin>>stations[i].first>>stations[i].second;
    }
    cin>>m;
   // cout<<m<<endl;
    for(i=1;i<=m;i++)
    {
        cin>>b[i].L>>b[i].R;
        b[i].len = 0;
        b[i].curr=-1;
        b[i].time = 0;
    }
    cin>>t>>f;
    for(i=1;i<=f;i++)
    {
        cin>>tour[i].time>>tour[i].st>>tour[i].num;
    }
    cin>>d;
}
bool cmptour(tourists i, tourists j)
{
    if(i.time==j.time)return i.num>j.num;
    return i.time<j.time;
}
bool check(int buss, int st)
{
    for(int i=0; i< b[buss].stat.size();i++)
    {
        if(b[buss].stat[i]==st)return true;
    }
    return false;
}
int dist(int a, int b)
{
    if(a==-1||b==-1)return 0;

    return abs(stations[a].first-stations[b].first)+ abs(stations[a].second-stations[b].second);
}
void put(int buss, int t)
{
    //cout<<"ADD "<<t<<" TO "<<buss<<endl;
     if(b[buss].curr==-1)b[buss].starttime = tour[t].time;
    b[buss].len+= dist(b[buss].curr,tour[t].st);
    b[buss].stat.push_back(tour[t].st);
    b[buss].time+=dist(b[buss].curr,tour[t].st);
    b[buss].curr = tour[t].st;
    b[buss].clients.push_back(t);
    return;
}
void putstat(int buss, int t)
{
    //cout<<"ADD "<<t<<" TO "<<buss<<endl;
    if(b[buss].curr==-1)b[buss].starttime = t;
    b[buss].len+= dist(b[buss].curr,t);
    b[buss].stat2.push_back(t);


    b[buss].curr = t;

    return;
}
void clearall()
{
    int i;
    for(i=1;i<=m;i++)
    {
        b[i].clients.clear();
        b[i].curr = -1;
        b[i].len=0;
        b[i].starttime=0;
        b[i].stat.clear();
        b[i].time=0;

    }
    return ;
}
void clearall2()
{
    int i;
    for(i=1;i<=m;i++)
    {
        b[i].clients.clear();
        b[i].curr = -1;
        b[i].len=0;
        b[i].starttime=0;
        b[i].stat2.clear();
        b[i].times2.clear();
        b[i].time=0;

    }
    return ;
}
bool fl=true;
void calcfor(int v)
{
    int time = tour[v].time;
    int st  = tour[v].st;
    int mintime = 1e9, buss;
    int i;
  // while(1)
  for(int br=1;br<=MAX;br++)
    {
        i = Rand()%m+1;
        int t = b[i].time+dist(b[i].curr,st);
       // cout<<v<<" && "<<i<<" && "<<t<<endl;
        if(check(i,st)){b[i].clients.push_back(v);return ;}
        if((b[i].len + dist(b[i].curr,st) + (b[i].stat.size()==0 ? 0 : dist(b[i].stat[0],st))) < b[i].L){put(i,v);return ;}

    }
    clearall();
    fl=false;
    return ;
}
void solve()
{
    for(int i = 1; i <= f&&fl; i++)
    {
        calcfor(i);
    }
    if(!fl){fl=true;solve();}
}
void print()
{

    int i,j;
    for(i=1;i<=m;i++)
    {
        cout<<b[i].stat.size()<<" ";
        for(j=0;j<b[i].stat.size();j++)cout<<b[i].stat[j]<<" ";

        cout<<endl;
        cout<<b[i].times.size()<<" ";
        for(j=0;j<b[i].times.size();j++)cout<<b[i].times[j]<<" ";
        cout<<endl;
    }
}int TIMES[1005];
void calcwhole(int v)
{
    int prev=-1;
    b[v].whole=0;
    for(int i=0; i<b[v].stat.size();i++){
            b[v].whole+=dist(prev,b[v].stat[i]);
            if(i+1<b[v].stat.size())
            TIMES[b[v].stat[i]] = b[v].whole;
          //  cout<<"BUSS: " <<b[v].stat[i]<<" "<<TIMES[b[v].stat[i]]<<endl;

    prev=b[v].stat[i];
    }
    b[v].whole+=b[v].R;
}
void calcwhole2(int v)
{
    int prev=-1;
    b[v].whole=0;
    for(int i=0; i<b[v].stat2.size();i++){
         //   cout<<prev<<"**"<<b[v].stat2[i]<<" "<<dist(prev,b[v].stat2[i])<<endl;
            b[v].whole+=dist(prev,b[v].stat2[i]);
            if(i+1<b[v].stat2.size())
            TIMES[b[v].stat2[i]] = b[v].whole;
           // cout<<"BUSS: " <<b[v].stat2[i]<<" "<<TIMES[b[v].stat2[i]]<<endl;

    prev=b[v].stat2[i];
    }
    b[v].whole+=b[v].R;
}
vector <pair <int,int>> sta;


vector <int> swv;
vector <int> V;
int vis[1005],visid=1;
void addstation(int v, int BUSS)
{
int i;
        vis[v]=visid;
       //cout<<"&& "<<v<<endl;
        putstat(BUSS,v);
        int mindist=1e9, u;
                for(i=0;i<V.size();i++)
        {
            if(vis[V[i]]==visid)continue;
            if(mindist>dist(v,V[i]))
            {
                mindist=dist(v,V[i]);
                u = V[i];
            }
        }
        if(mindist==1e9)return ;
        addstation(u,BUSS);
}
void solvefor1bus(int BUSS)
{
    int i;
    if(m==1)
    for(i=1;i<=f;i++)
    {
        b[BUSS].clients.push_back(i);

    }
    b[BUSS].curr=-1;
    visid++;
    swv.clear();
    for(i=0;i<b[BUSS].clients.size();i++)
        swv.push_back(tour[b[BUSS].clients[i]].st);
    sort(swv.begin(),swv.end());
    V.clear();
    V.push_back(swv[0]);
    for(i=1;i<swv.size();i++)
        if(swv[i]!=swv[i-1])V.push_back(swv[i]);

    int v;
    addstation(V[0],BUSS);
}
void swapit(int BUSS)
{
   // cout<<"OK"<<endl;
    int i;
    b[BUSS].times.clear();
    for(i=0;i<b[BUSS].times2.size();i++)
    {

         b[BUSS].times.push_back(b[BUSS].times2[i]);
    }


    b[BUSS].stat.clear();
    for(i=0;i<b[BUSS].stat2.size();i++)
    {  //cout<<b[BUSS].stat2[i]<<" ";
        b[BUSS].stat.push_back(b[BUSS].stat2[i]);
    }//cout<<endl;
}
void recalc()
{
    int i,j;

    for(i=1;i<=m;i++)
    {
       // b[i].clients.clear();
        sta.clear();
        if(b[i].stat.size()>0)b[i].stat.push_back(b[i].stat[0]);

        calcwhole(i);
        for(j=0;j<b[i].clients.size();j++)
        {
            int v = b[i].clients[j];
           // cout<<"buss: "<<i<<" "<<"client " << v<< " "<<TIMES[tour[v].st]<<endl;
            sta.push_back({max(1,tour[v].time-TIMES[tour[v].st]),v});


        } sort(sta.begin(),sta.end());
        for(j=0;j<sta.size()-1;j++)
        {
           // cout<<"******"<<i<<" "<<sta[j]<<endl;
            if(sta[j].first+b[i].whole<=sta[j+1].first)b[i].times.push_back(sta[j].first);
        }
        if(sta.size()>0)
        b[i].times.push_back(sta[sta.size()-1].first);
        long long ANS = 0;
        int k = 0;
        for(j=0;j<sta.size();j++)
        {
            if(b[i].times[k]<sta[j].first)k++;
            ANS = ANS + (long long)((long long)b[i].times[k]-(long long)sta[j].first)*(long long)sta[j].second;
        }


        ////////////////////////////////////////////////////////////////////////////////////////////////
       if(m!=1)
        solvefor1bus(i);
         sta.clear();
        if(b[i].stat2.size()>0)b[i].stat2.push_back(b[i].stat2[0]);

        calcwhole2(i);
        for(j=0;j<b[i].clients.size();j++)
        {
            int v = b[i].clients[j];
           // cout<<"buss: "<<i<<" "<<"client " << v<< " "<<TIMES[tour[v].st]<<endl;
            sta.push_back({max(1,tour[v].time-TIMES[tour[v].st]),v});


        } sort(sta.begin(),sta.end());
        for(j=0;j<sta.size()-1;j++)
        {
           // cout<<"******"<<i<<" "<<sta[j]<<endl;
            if(sta[j].first+b[i].whole<=sta[j+1].first)b[i].times2.push_back(sta[j].first);
        }
        if(sta.size()>0)
        b[i].times2.push_back(sta[sta.size()-1].first);
        long long ANS2 = 0;
         k = 0;
        for(j=0;j<sta.size();j++)
        {
            if(b[i].times2[k]<sta[j].first)k++;
            ANS2 = ANS2 + (long long)((long long)b[i].times2[k]-(long long)sta[j].first)*(long long) sta[j].second;
        }
        if(ANS2<ANS||m==1)
            swapit(i);
            }
}
stack <int> st;
struct CLIENTSONSTATION
{
    int num;
    vector <int> st;
    vector <int> times;
    vector <int> clients;
    int mindist;
};
CLIENTSONSTATION CL[1005];
vector <CLIENTSONSTATION> vect;
bool cmpCLIENTSONSTATION(CLIENTSONSTATION i, CLIENTSONSTATION j)
{
    if(i.mindist==j.mindist)return i.num<j.num;
    return i.mindist<j.mindist;
}
vector <pair<int, int> > bvect;
long long calcANS(int v)
{
   // cout<<"&&&&&&&&&&&& "<<v<<endl;
    calcwhole2(v);
    int i;
    int k = 0;
    long long ANS = 0;
    for(i=0;i<b[v].clients.size();i++)
    {
        int u = b[v].clients[i];
        while(b[v].times2[k]+TIMES[tour[u].st]<tour[u].time)k++;
      //  cout<<" && && "<<u<<" "<<b[v].times2[k]<<" "<<TIMES[tour[u].st]<<" "<<tour[u].time<<endl;
        //cout<<u<<" "<<(long long)((long long)-tour[u].time+(long long)(b[v].times2[k]+TIMES[tour[u].st]))*(long long)tour[u].num<<endl;
        ANS+=(long long)((long long)-tour[u].time+(long long)(b[v].times2[k]+TIMES[tour[u].st]))*(long long)tour[u].num;
    }
    return ANS;
}
bool checkforenoughbusses()
{
    visid++;
    int i,br=0;
    for(i=1;i<=n;i++)
    {
        CL[i].mindist=1e9;
        CL[i].num = i;
    }

    for(i=1;i<=f;i++)
    {
        CL[tour[i].st].st.push_back(tour[i].time);
        CL[tour[i].st].clients.push_back(i);
        if(vis[tour[i].st]!=visid){vis[tour[i].st]=visid; br++;}
    }

    if(br>m)return false;
    int j;
    for(i=1;i<=n;i++)
    {
        if(CL[i].st.size()==0)continue;
        sort(CL[i].st.begin(),CL[i].st.end());
        CL[i].times.push_back(CL[i].st[0]);
        for(j=1;j<CL[i].st.size();j++)
        {
            if(CL[i].st[j]==CL[i].st[j-1])continue;
            CL[i].mindist = min(CL[i].mindist,CL[i].st[j]-CL[i].st[j-1]);
            CL[i].times.push_back(CL[i].st[j]);
        }
        vect.push_back(CL[i]);
    }
    sort(vect.begin(),vect.end(),cmpCLIENTSONSTATION);
    for(i=1;i<=m;i++)
    bvect.push_back({b[i].R,i});
    sort(bvect.begin(),bvect.end());
    for(i=0;i<vect.size();i++)
    {
        int buss = bvect[i].second;
        b[buss].stat2.push_back(vect[i].num);
        b[buss].stat2.push_back(vect[i].num);
        st.push(vect[i].times[vect[i].times.size()-1]);
        for(j= vect[i].times.size()-2;j>=0;j--)
        {
            if(vect[i].times[j+1]-vect[i].times[j]>bvect[i].first)
            {
                st.push(vect[i].times[j]);
            }
        }
        while(!st.empty())
        {
            b[buss].times2.push_back(st.top());
            st.pop();
        }
        for(j=0;j<vect[i].clients.size();j++)
            b[buss].clients.push_back(vect[i].clients[j]);
    }
    long long ANS = 0;
    for(i=1;i<=m;i++)
    {
        ANS+=calcANS(i);
    }
    if(ANS<BESTANS)
    {
        for(i=1;i<=m;i++)swapit(i);
        BESTANS=ANS;

    }

   /* memset(vis,0,sizeof(vis));
    int nbr=br;
    br=0;
    for(i=1;i<=f;i++)
    {
        int u = tour[i].st;
        if(vis[u]==0){br++;vis[u]=br;  b[vis[u]].stat.push_back(u);
        b[vis[u]].stat.push_back(u);}
        else
            if(tour[i].time - b[vis[u]].clients[b[vis[u]].clients.size()-1]<b[vis[u]].R&& tour[i].time - b[vis[u]].clients[b[vis[u]].clients.size()-1]>0)
        {
            if(nbr<m)
            {
                nbr++;
                br++;
                vis[u]=br;
                b[vis[u]].stat.push_back(u);
        b[vis[u]].stat.push_back(u);
            }
        }
        b[vis[u]].clients.push_back(i);

        b[vis[u]].times2.push_back(tour[i].time);
    }
    for(i=1;i<=m;i++)
    {
        if(b[i].times2.size()==0)continue;
        sort(b[i].times2.begin(),b[i].times2.end());
        st.push(b[i].times2[b[i].times2.size()-1]);
        for(int j=b[i].times2.size()-2;j>=0;j--)
        {
            if(b[i].times2[j]+b[i].R<=b[i].times2[j+1])st.push(b[i].times2[j]);
        }
        while(!st.empty())
        {
            b[i].times.push_back(st.top());
            st.pop();
        }
    }*/
    return true;
}
bool checkforenoughbussesprev()
{
    memset(vis,0,sizeof(vis));
    visid++;
    int i,br=0;
    for(i=1;i<=f;i++)
    {
        if(vis[tour[i].st]!=visid){vis[tour[i].st]=visid; br++;}
    }
    if(br>m)return false;

    memset(vis,0,sizeof(vis));
    int nbr=br;
    br=0;
    for(i=1;i<=m;i++)
    {
        b[i].stat2.clear();
        b[i].times2.clear();
        b[i].clients.clear();
    }
    for(i=1;i<=f;i++)
    {
        int u = tour[i].st;
        if(vis[u]==0){br++;vis[u]=br;  b[vis[u]].stat2.push_back(u);
        b[vis[u]].stat2.push_back(u);}
        else
            if(tour[i].time - b[vis[u]].clients[b[vis[u]].clients.size()-1]<b[vis[u]].R&& tour[i].time - b[vis[u]].clients[b[vis[u]].clients.size()-1]>0)
        {
            if(nbr<m)
            {
                nbr++;
                br++;
                vis[u]=br;
                b[vis[u]].stat2.push_back(u);
        b[vis[u]].stat2.push_back(u);
            }
        }
        b[vis[u]].clients.push_back(i);

        b[vis[u]].times2.push_back(tour[i].time);
    }
    for(i=1;i<=m;i++)
    {
        if(b[i].times2.size()==0)continue;
        sort(b[i].times2.begin(),b[i].times2.end());
        st.push(b[i].times2[b[i].times2.size()-1]);
        for(int j=b[i].times2.size()-2;j>=0;j--)
        {
            if(b[i].times2[j]+b[i].R<=b[i].times2[j+1])st.push(b[i].times2[j]);
        }
        b[i].times2.clear();
        while(!st.empty())
        {
            b[i].times2.push_back(st.top());
            st.pop();
        }
    }
    long long ANS = 0;
    for(i=1;i<=m;i++)ANS+=calcANS(i);
    if(ANS<BESTANS)
    {
        BESTANS = ANS;
        for(i=1;i<=m;i++)
        swapit(i);
    }
    return true;
}
set <int> SET;
pair <long long,int> dp[1005];
void calcdp(int v)
{
    int i,j;
    for(i=0;i<b[v].swv.size();i++)
    {
        dp[i].first = 1e18;
        dp[i].second = -1;
    }
    dp[0].first = 0;
    dp[0].second  = -1;


    for(i=1;i<b[v].swv.size();i++)
    {

 long long minans=1e18,sum=0;   int ids=-1;
        for(j=i-1;j>=0;j--)
        {
            if(b[v].swv[i].first-b[v].swv[j].first>=b[v].whole)
            {
                if(minans>(sum+dp[j].first))
                {
                    minans=sum+dp[j].first;
                    ids = j;
                }
            }
            sum+=(b[v].swv[i].first-b[v].swv[j].first)*b[v].swv[j].second;
        }
        if(minans>sum)
                {
                    minans=sum;
                    ids = -1;
                }
        dp[i].first= minans;
        dp[i].second = ids;
    }
    int k = b[v].swv.size()-1;
    while(k!=-1)
    {
        b[v].times2.push_back(b[v].swv[k].first);
        k = dp[k].second;
    }
    sort(b[v].times2.begin(),b[v].times2.end());
}
void solveaddstationswhileyoucan(int maxnum)
{
    clearall2();
    memset(vis,0,sizeof(vis));
    int i,j;
    SET.clear();

    for(i=1;i<=f;i++)
        SET.insert(tour[i].st);

    for(i=1;i<=m;i++)
    {
        b[i].swv.clear();
        int v=-1;
        int x = 1e9,y=1e9;
    for(auto it:SET){if(vis[it]==0){
            if(stations[it].first<x||(stations[it].first==x&&stations[it].second<y))
            {
                x=stations[it].first;
                y=stations[it].second;
                v=it;
            }
            }}

   // cout<<"V: "<<v<<endl;
    //SET.erase(SET.begin());
    if(v==-1)break;
    putstat(i,v);

    vis[v]=i;
    for(int K=2;K<=maxnum;K++){
    int mindist=1e9,ids=-1;
        for(auto it:SET)
        { //for(auto itt=SET.begin();itt!=SET.end();++itt)cout<<*itt<<endl;
            v = it;
            if(vis[v])continue;
            if(dist(b[i].curr,v)+dist(b[i].starttime,v)<mindist)
            {
                mindist=dist(b[i].curr,v)+dist(b[i].starttime,v);
                ids=v;
            }
           // cout<<"V:& "<<v<<endl;

        }
        if(ids==-1)break;
        v=ids;
        if(b[i].len+dist(b[i].curr,v)+dist(b[i].starttime,v)<=b[i].L)
            {
               // SET.erase(it);
                putstat(i,v);
                vis[v]=i;
            }else
            break;
    }
    }
    for(i=1;i<=f;i++)
    {
        if(vis[tour[i].st]==0)return ;
        b[vis[tour[i].st]].clients.push_back(i);
    }
    long long sum = 0;
    for(i=1;i<=m;i++)
    {

        if(b[i].stat2.size()>0)b[i].stat2.push_back(b[i].stat2[0]);
        calcwhole2(i);
        sum+=(b[i].whole-b[i].R);

    }
    for(i=1;i<=m;i++)
    {

        b[i].swv.clear();
        if(b[i].stat2.size()==0)continue;
        calcwhole2(i);//cout<<i<<endl;
        for(j=0;j<b[i].clients.size();j++)
        {
            int v = b[i].clients[j];
            b[i].swv.push_back({max(tour[v].time-TIMES[tour[v].st],1),v});
        }
        sort(b[i].swv.begin(),b[i].swv.end());
if(d!=-1)
       b[i].times2.push_back(b[i].swv[b[i].swv.size()-1].first);
    }
    if(d==-1)
    {
        for(i=1;i<=m;i++)
            calcdp(i);
    }else
    while(d==-1||sum<d)
    {
       /* cout<<"*******************************"<<endl;
        for(i=1;i<=m;i++)
        {
            cout<<i<<" : ";
            for(j=0;j<b[i].times2.size();j++)
                cout<<b[i].times2[j]<<" ";
            cout<<endl;
        }
        cout<<"*********************************"<<endl;*/
        long long maxs=0,ids=-1,pos,w,k=0,br=0;
        for(i=1;i<=m;i++)
        {
            k=0;
            br=0;
            if(sum+b[i].whole>d)continue;
            for(j=0;j<b[i].swv.size();j++)
            {
                while(b[i].swv[j].first>b[i].times2[k]){k++;br=0;}
               // cout<<"** "<<i<<" "<<b[i].swv[j].first<<" & "<<b[i].times2[k]<<endl;
                br+=tour[b[i].swv[j].second].num;
                if(b[i].swv[j].first+b[i].whole>=b[i].times2[k]||(k>0&&b[i].times2[k-1]+b[i].whole>=b[i].swv[j].first))continue;
                if((b[i].times2[k]-b[i].swv[j].first)*br>maxs)
                {
                    maxs = (b[i].times2[k]-b[i].swv[j].first)*br;
                    ids = i;
                    pos = b[i].swv[j].first;
                }
            }
        }
        if(ids==-1)break ;
       // cout<<ids<<" & "<<pos<<endl;
        sum+=(b[ids].whole-b[ids].R);
        b[ids].times2.push_back(pos);
        sort(b[ids].times2.begin(),b[ids].times2.end()); //cout<<"ADD"<< ids<<" "<<pos<<endl;
    }
   //  cout<<"**"<<ANS<<endl;
        long long ANS=0;
    for(i=1;i<=m;i++)
    {
     //   cout<<i<<" "<<calcANS(i)<<endl;
         ANS += calcANS(i);
    }

    if(ANS<BESTANS)
    {
        BESTANS=ANS;
         for(i=1;i<=m;i++)
    swapit(i);
    }


}
void solveaddstationswhileyoucanold()
{
    clearall2();
    SET.clear();
    memset(vis,0,sizeof(vis));
    int i,j;
    for(i=1;i<=f;i++)
        SET.insert(tour[i].st);

    for(i=1;i<=m;i++)
    {
        int v=-1;
        int x = 1e9,y=1e9;
    for(auto it:SET){if(vis[it]==0){
            if(stations[it].first<x||(stations[it].first==x&&stations[it].second<y))
            {
                x=stations[it].first;
                y=stations[it].second;
                v=it;
            }
            }}

   // cout<<"V: "<<v<<endl;
    //SET.erase(SET.begin());
    if(v==-1)break;
    putstat(i,v);

    vis[v]=i;
    while(1){
    int mindist=1e9,ids=-1;
        for(auto it:SET)
        { //for(auto itt=SET.begin();itt!=SET.end();++itt)cout<<*itt<<endl;
            v = it;
            if(vis[v])continue;
            if(dist(b[i].curr,v)+dist(b[i].starttime,v)<mindist)
            {
                mindist=dist(b[i].curr,v)+dist(b[i].starttime,v);
                ids=v;
            }
           // cout<<"V:& "<<v<<endl;

        }
        if(ids==-1)break;
        v=ids;
        if(b[i].len+dist(b[i].curr,v)+dist(b[i].starttime,v)<=b[i].L)
            {
               // SET.erase(it);
                putstat(i,v);
                vis[v]=i;
            }else
            break;
    }
    }
    for(i=1;i<=f;i++)
    {
        b[vis[tour[i].st]].clients.push_back(i);
    }
    long long sum = 0;
    for(i=1;i<=m;i++)
    {

        if(b[i].stat2.size()>0)b[i].stat2.push_back(b[i].stat2[0]);
        calcwhole2(i);
        sum+=b[i].whole-b[i].R;
    }
    for(i=1;i<=m;i++)
    {

        swv.clear();
        if(b[i].stat2.size()==0)continue;
        calcwhole2(i);//cout<<i<<endl;
        for(j=0;j<b[i].clients.size();j++)
        {
            int v = b[i].clients[j];
            swv.push_back(max(tour[v].time-TIMES[tour[v].st],1));
        }
        sort(swv.begin(),swv.end());

        st.push(swv[swv.size()-1]);
        for(j=swv.size()-2;j>=0;j--)
        {
            if(swv[j]+b[i].whole<=st.top()&&(sum+b[i].whole-b[i].R<=d)){sum+=(b[i].whole-b[i].R);st.push(swv[j]);}
        }
        while(!st.empty())
        {

          b[i].times2.push_back(st.top());st.pop();}
    }
    long long ANS=0;
    for(i=1;i<=m;i++)
    {
     //   cout<<i<<" "<<calcANS(i)<<endl;
         ANS += calcANS(i);
    }

   //  cout<<"**"<<ANS<<endl;
    if(ANS<BESTANS)
    {
        BESTANS=ANS;
         for(i=1;i<=m;i++)
    swapit(i);
    }


}
void solveaddstationswhileyoucanprev(int maxnum)
{
    clearall2();
    SET.clear();
    memset(vis,0,sizeof(vis));
    int i,j;
    for(i=1;i<=f;i++)
        SET.insert(tour[i].st);

    for(i=1;i<=m;i++)
    {

        int v=-1;
    int x = 1e9,y=1e9;
    for(auto it:SET){if(vis[it]==0){
            if(stations[it].first<x||(stations[it].first==x&&stations[it].second<y))
            {
                x=stations[it].first;
                y=stations[it].second;
                v=it;
            }
            }}
   // cout<<"V: "<<v<<endl;
    //SET.erase(SET.begin());
    if(v==-1)break;
    putstat(i,v);

    vis[v]=i;
    //while(1)
        int K=1;
        for(auto it=SET.begin();it!=SET.end()&&K<maxnum;it++)
        { //for(auto itt=SET.begin();itt!=SET.end();++itt)cout<<*itt<<endl;
            v = *it;
            if(vis[v])continue;
           // cout<<"V:& "<<v<<endl;
            if(b[i].len+dist(b[i].curr,v)+dist(b[i].starttime,v)<=b[i].L)
            {
               // SET.erase(it);
                putstat(i,v);
                vis[v]=i;
            }
        }
    }
    for(i=1;i<=f;i++)
    {
        if(vis[tour[i].st]==0)return ;
        b[vis[tour[i].st]].clients.push_back(i);
    }
    long long sum = 0;
    for(i=1;i<=m;i++)
    {

        if(b[i].stat2.size()>0)b[i].stat2.push_back(b[i].stat2[0]);
        calcwhole2(i);
        sum+=b[i].whole-b[i].R;
    }
    for(i=1;i<=m;i++)
    {

        swv.clear();
        if(b[i].stat2.size()==0)continue;
        calcwhole2(i);//cout<<i<<endl;
        for(j=0;j<b[i].clients.size();j++)
        {
            int v = b[i].clients[j];
            swv.push_back(max(tour[v].time-TIMES[tour[v].st],1));
        }
        sort(swv.begin(),swv.end());

        st.push(swv[swv.size()-1]);
        for(j=swv.size()-2;j>=0;j--)
        {
            if(swv[j]+b[i].whole<=st.top()&&(sum+b[i].whole-b[i].R<=d)){sum+=(b[i].whole-b[i].R);st.push(swv[j]);}
        }
        while(!st.empty())
        {

          b[i].times2.push_back(st.top());st.pop();}
    }
     long long ANS=0;
    for(i=1;i<=m;i++)
    ANS += calcANS(i);
    //cout<<"**"<<ANS<<endl;
    if(ANS<BESTANS)
    {
        BESTANS=ANS;
         for(i=1;i<=m;i++)
    swapit(i);
    }

}
int main()
{
  freopen ("wonderland.out","w",stdout);
 freopen ("wonderland.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();  int i,j;
sort(tour+1, tour + f+1, cmptour);
if(checkforenoughbusses())
    {
       checkforenoughbussesprev();
        print();
        return 0;
    }
for(i=1;i<=m;i++)b[i].clients.clear();
 /*  if(m==1){solvefor1bus(1);recalc();
    print();return ;}*/
    //else
  {
   //   cout<<"THISCASE"<<endl;
   for(i=1;i<=f&&( float( clock () - begin_time ) /  CLOCKS_PER_SEC<Time);i++)
 solveaddstationswhileyoucan(i);
 solveaddstationswhileyoucanold();
 for(i=1;i<=f&&( float( clock () - begin_time ) /  CLOCKS_PER_SEC<Time);i++)
 solveaddstationswhileyoucanprev(i);
 //cout<<"ENDTHISCASE"<<endl;
    //solve();
  }

 //   recalc();
 //cout<<BESTANS<<endl;
    print();
    }
/*
5
1 1
 2 2
3 3
4 4
5 5
3
10 2
30 5
40 1
200 5
1 1 10
4 1 15
1 2 10
1 3 15
20 2 6
100
*/