Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=1e6+5;
const int imax=1e6;
const int inf=999999999;
int en,n,a[maxn],b[maxn];
typedef long long ll;
ll tree[maxn],sum[maxn],c[maxn];

/*struct node
{
	int x,id;
//	node(int x,int id):x(x),id(id){}
}p[maxn];*/

struct node
{
    int x,id;
    node(){}
    bool operator < (const node &a) const
    {
        if(a.x==x) return id<a.id;
        return x>a.x;
    }
}p[maxn];

bool cmp(node a,node b)
{
	return a.x==b.x?a.id<b.id:a.x>b.x;
}


void build(int l,int r,int rt)
{
	if(l==r)
	{
		tree[rt]=sum[l]-c[l-1];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt*2);
	build(mid+1,r,rt*2+1);
	tree[rt]=min(tree[rt*2],tree[rt*2+1]); 
}

ll qu(int L,int R,int l,int r,int rt)
{
	if(L>R)	return inf;
	if(r<L||l>R)	return inf;
	if(l>=L&&r<=R)	return tree[rt];
	int mid=(l+r)>>1;
	int a1=inf,a2=inf;
	a1=qu(L,R,l,mid,rt*2);
	a2=qu(L,R,mid+1,r,rt*2+1);
	return min(a1,a2);
}

bool check(int i,int mid)
{
    if(i>mid) return sum[mid]+a[p[i].id]>=en;
    return sum[mid]-p[i].x+a[p[i].id]>=en;
}


int main()
{
	int ans=inf;
	c[0]=0;
	sum[0]=0;
	scanf("%d%d",&n,&en);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",a+i,b+i);
		p[i].x=a[i]-b[i];
		p[i].id=i;
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",c+i);
		c[i]+=c[i-1];
	}
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;++i)	sum[i]=sum[i-1]+p[i].x;
	build(1,n,1);
	int gg=n;
	for(int i=1;i<=n;++i)
	{
		if(p[i].x<0)
		{
			gg=i;
			break;
		}
		
	}
	gg++;
	int num=1;
	while(sum[num]>c[num])
	{
		if(num>n)	break;
		num++;
	}
	for(int i=1;i<=n;++i)
	{
		int l=0,r=n+1;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(check(i,mid))	r=mid;
			else l=mid+1;
		}
		if(r>n)	continue;
		if(r<i)
		{
			if(r<num)	ans=min(ans,r+1);
		}
		else
		if(qu(i+1,r,1,n,1)>p[i].x)	ans=min(ans,r);
	}
	if(ans==inf)	printf("-1\n");
	else printf("%d\n",ans);
	return 0;
}