Description：

$n$ 种果汁，每种有价值，价格和限量，混合果汁的价值是所有果汁的最小值，多次询问用不超过 $k$ 元钱，至少买 $v$ 升能得到的混合果汁的最大价值。

$1\leqslant n\leqslant 10^5$

Solution：

最大值最小显然是二分，二分答案之后就是判断只用 $v\geqslant d$ 的果汁用不超过 $k$ 元钱能买到的最多的体积，显然我们应该按价格排序然后贪心，这个可以用在主席树上二分的方法实现，时间复杂度 $O(n\log ^2n)$ ，空间复杂度 $O(n\log^2n)$ 。

一个更好的做法是整体二分，对于当前二分的这个值，把所有在这个区间中的 $v\geqslant d$ 的果汁都加到一棵线段树里去，然后在线段树上二分，递归的时候 先进入大的部分 ， 在叶子节点把这个值加入线段树 ，这样在每个点的线段树中查到的就是所有 $v\geqslant d$ 的答案了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct juice

{

	int val,pri,lim;

}c[MAXN],c1[MAXN],c2[MAXN];

bool cmp_pri(juice a,juice b){return a.pri < b.pri;}

typedef long long ll;

struct query

{

	ll cos,vol;

	int id;

}q[MAXN],q1[MAXN],q2[MAXN];

int ans[MAXN];

#define INF 0x3f3f3f3f

struct node

{

	int lc,rc;

	ll sump,sumv;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

#define N 100000

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int p,int k,int l,int r)

{

	if(l == r)

	{

		t[rt].sump += 1ll * p * k;

		t[rt].sumv += k;

		return;

	}

	if(p <= mid)add(t[rt].lc,p,k,l,mid);

	else add(t[rt].rc,p,k,mid + 1,r);

	t[rt].sump = t[t[rt].lc].sump + t[t[rt].rc].sump;

	t[rt].sumv = t[t[rt].lc].sumv + t[t[rt].rc].sumv;

	return;

}

ll query(int rt,ll g,int l,int r)

{

	if(g >= t[rt].sump)return t[rt].sumv;

	if(l == r)return (g / l);

	ll ls = t[t[rt].lc].sump;

	if(g > ls)return query(t[rt].rc,g - ls,mid + 1,r) + t[t[rt].lc].sumv;

	else return query(t[rt].lc,g,l,mid);

}

void solve(int lc,int rc,int lq,int rq,int L,int R)

{

	if(L == R)

	{

		for(int i = lc;i <= rc;++i)add(root,c[i].pri,c[i].lim,1,N);

		for(int i = lq;i <= rq;++i)

		{

			if(query(root,q[i].cos,1,N) >= q[i].vol)ans[q[i].id] = L;

			else ans[q[i].id] = -1;

		}

		return;

	}

	int midd = ((L + R + 1) >> 1);

	int ccnt1 = 0,ccnt2 = 0;

	int qcnt1 = 0,qcnt2 = 0;

	for(int i = lc;i <= rc;++i)

	{

		if(c[i].val >= midd)c2[++ccnt2] = c[i];

		else c1[++ccnt1] = c[i];

	}

	for(int i = 1;i <= ccnt2;++i)add(root,c2[i].pri,c2[i].lim,1,N);

	for(int i = lq;i <= rq;++i)

	{

		if(query(root,q[i].cos,1,N) >= q[i].vol)q2[++qcnt2] = q[i];

		else q1[++qcnt1] = q[i];

	}

	for(int i = 1;i <= ccnt2;++i)add(root,c2[i].pri,-c2[i].lim,1,N);

	int ccur = lc;

	for(int i = 1;i <= ccnt1;++i)c[ccur++] = c1[i];

	for(int i = 1;i <= ccnt2;++i)c[ccur++] = c2[i];

	int qcur = lq;

	for(int i = 1;i <= qcnt1;++i)q[qcur++] = q1[i];

	for(int i = 1;i <= qcnt2;++i)q[qcur++] = q2[i];

	solve(lc + ccnt1,rc,lq + qcnt1,rq,midd,R);

	solve(lc,lc + ccnt1 - 1,lq,lq + qcnt1 - 1,L,midd - 1);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int maxval = 0;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d",&c[i].val,&c[i].pri,&c[i].lim);

		maxval = max(maxval,c[i].val);

	}

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

	{

		scanf("%lld%lld",&q[i].cos,&q[i].vol);

		q[i].id = i;

	}

	build(root,1,N);

	solve(1,n,1,m,1,maxval);

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

	{

		printf("%d\n",ans[i]);

	}

	return 0;

}