1 // 离线树状数组 hihocoder 1391 Countries 2  3 #include <iostream> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <algorithm> 7 #include <vector> 8 #include <math.h> 9 #include <memory.h>10 using namespace std;11 #define LL long long12 typedef pair<int,int> pii;13 const LL inf = 0x3f3f3f3f;14 const LL MOD =100000000LL;15 // const int N = 1e5+10;16 const double eps = 1e-8;17 void fre() {freopen("in.txt","r",stdin);}18 void freout() {freopen("out.txt","w",stdout);}19 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}20 const int MAXN = 60010;21 struct node{22     LL l,r,v;23 }N[MAXN];24 25 LL f[MAXN],x[MAXN];26 int cmp(node a,node b){27     return a.r<b.r;28 }29 void add(LL w,LL v){30     for(;w<=MAXN;w+=w&(-w)) f[w]+=v;31 }32 LL getsum(LL w){33     LL sum=0;34     for(;w;w-=w&(-w)) sum+=f[w];35     return sum;36 }37 38 int main(){39     LL n,m,bs,nn,M;40     while(~scanf("%lld%lld",&n,&m)){41         memset(f,0,sizeof(f));42         memset(x,0,sizeof(x));43         scanf("%lld",&bs);44         scanf("%lld%lld",&nn,&M);45         LL r=m+bs;46         LL k=0;47         LL sum=0;48         for(LL i=1;i<=nn;i++){49             LL s,t,v;50             scanf("%lld%lld%lld",&s,&t,&v);51             if(s+t<bs||s+t>r) continue;52             else{53                 N[++k].l=s+2*t,N[k].r=s+2*t+(r-s-t)/(2*t)*2*t;54                 N[k].v=v;55                 sum+=v;56             }57         }58         for(LL i=1;i<=M;i++){59             LL s,t,v;60             scanf("%lld%lld%lld",&s,&t,&v);61             N[++k].l=s+t,N[k].v=v;62             sum+=v;63             if(s+t*2<bs||s+t*2>r) N[k].r=N[k].l;64             else{65                 N[k].r=s+3*t+(r-s-2*t)/(2*t)*2*t;66             }67         }68         LL g=k;69         k=0;70         for(LL i=1;i<=g;i++){71             x[++k]=N[i].l,x[++k]=N[i].r,x[++k]=N[i].r-n;72         }73         sort(N+1,N+1+g,cmp);74         sort(x+1,x+1+k);75         k=unique(x+1,x+1+k)-x-1;76         LL ans=-inf;77         for(LL i=1;i<=g;i++){78             LL w,pre,now;79             w=lower_bound(x+1,x+1+k,N[i].l)-x;80             now=lower_bound(x+1,x+1+k,N[i].r)-x;81             pre=lower_bound(x+1,x+1+k,N[i].r-n)-x;82             add(w,N[i].v);83             ans=max(ans,getsum(now)-getsum(pre-1));84         }85         printf("%lld\n",sum-ans);86     }87     return 0;88 }