#include<bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define ll long long
using namespace std;
template <class T> inline T read(){
    T r=0,f=0; char c=getchar();
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) r=r*10+(c&15),c=getchar();
    return f?-r:r;
}
const int _=2e5+5,__=1e7+8e6;
int n,m,a[_],b[_],maxh,id[_];
int rt[1000005],ls[__],rs[__],cnt[__],tot;
ll s[_],sa[_],sumaa[__],suma[__];
inline ll f(ll a,int h){
    return a>h?(a+a-h+1)*h/2:(a+1)*a/2;
}
void upd(int &x,int y,int l,int r,int p,int v){
    x=++tot,sumaa[x]=sumaa[y]+1ll*(v+1)*v/2,suma[x]=suma[y]+v,cnt[x]=cnt[y]+1,ls[x]=ls[y],rs[x]=rs[y];
    if(l==r) return;
    int mid=l+r>>1;
    p>mid?upd(rs[x],rs[y],mid+1,r,p,v):upd(ls[x],ls[y],l,mid,p,v);
}
ll getaa(int x,int l,int r,int xl,int xr){
    if(!x) return 0;
    if(xl<=l&&xr>=r) return sumaa[x];
    int mid=l+r>>1;
    return xl>mid?getaa(rs[x],mid+1,r,xl,xr):xr<=mid?getaa(ls[x],l,mid,xl,xr):getaa(ls[x],l,mid,xl,xr)+getaa(rs[x],mid+1,r,xl,xr);
}
ll geta(int x,int l,int r,int xl,int xr){
    if(!x) return 0;
    if(xl<=l&&xr>=r) return suma[x];
    int mid=l+r>>1;
    return xl>mid?geta(rs[x],mid+1,r,xl,xr):xr<=mid?geta(ls[x],l,mid,xl,xr):geta(ls[x],l,mid,xl,xr)+geta(rs[x],mid+1,r,xl,xr);
}
int getcnt(int x,int l,int r,int xl,int xr){
    if(!x) return 0;
    if(xl<=l&&xr>=r) return cnt[x];
    int mid=l+r>>1;
    return xl>mid?getcnt(rs[x],mid+1,r,xl,xr):xr<=mid?getcnt(ls[x],l,mid,xl,xr):getcnt(ls[x],l,mid,xl,xr)+getcnt(rs[x],mid+1,r,xl,xr);
}
bool check(ll L,ll R,int l,int r,ll v,int h){
    ll res=0;
    if(s[l-1]>=R){
        if(!b[l-1]){
            ll a1=R-s[l-2],a2=L-s[l-2]-1;
            res+=f(a1,h)-f(a2,h);
        }
        else{
            ll a1=s[l-1]-L+1,a2=s[l-1]-R;
            res+=f(a1,h)-f(a2,h);
        }
        return res>=v;
    }
    if(s[l-1]>=L){
        if(!b[l-1]){
            ll a1=a[l-1],a2=L-s[l-2]-1;
            res+=f(a1,h)-f(a2,h);
        }
        else{
            ll a1=s[l-1]-L+1;
            res+=f(a1,h);
        }
    }
    if(s[r]+1<=R){
        if(b[r+1]){
            ll a1=a[r+1],a2=s[r+1]-R;
            res+=f(a1,h)-f(a2,h);
        }
        else{
            ll a1=R-s[r];
            res+=f(a1,h);
        }
    }
    if(l<=r) res+=sa[r]-sa[l-1]-getaa(rt[h],1,n,l,r)+geta(rt[h],1,n,l,r)*h-1ll*(h-1)*h/2*getcnt(rt[h],1,n,l,r);
    return res>=v;
}
signed main(){
    n=read<int>(),m=read<int>();
    for(int i=1;i<=n;++i) maxh=max(maxh,a[i]=read<int>()),s[i]=s[i-1]+a[i],sa[i]=sa[i-1]+1ll*(a[i]+1)*a[i]/2,b[id[i]=i]=read<int>();
    sort(id+1,id+1+n,[](int x,int y){return a[x]<a[y];});
    for(int i=maxh,r=n;i>=1;--i){
        rt[i]=rt[i+1];
        while(r&&a[id[r]]==i) upd(rt[i],rt[i],1,n,id[r],a[id[r]]),--r;
    }
    while(m--){
        int l=1,r=maxh,mid,ans=-1;
        ll L=read<ll>(),R=read<ll>(),v=read<ll>();
        int LL=lower_bound(s+1,s+1+n,L)-s+1,RR=upper_bound(s+1,s+1+n,R)-s-1;
        while(l<=r) check(L,R,LL,RR,v,mid=l+r>>1)?r=(ans=mid)-1:l=mid+1;
        printf("%d\n",ans);
    }
    return 0;
}

1s极限数据真的卡不过去了，2s还行