CodeForces - 609D (二分！二分！)

╰半夏微凉° 2022-05-29 10:59 192阅读 0赞

D. Gadgets for dollars and pounds

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Nura wants to buy *k* gadgets. She has only *s* burles for that. She can buy each gadget for dollars or for pounds. So each gadget is selling only for some type of currency. The type of currency and the cost in that currency are not changing.

Nura can buy gadgets for *n* days. For each day you know the exchange rates of dollar and pound, so you know the cost of conversion burles to dollars or to pounds.

Each day (from 1 to *n*) Nura can buy some gadgets by current exchange rate. Each day she can buy any gadgets she wants, but each gadget can be bought no more than once during *n* days.

Help Nura to find the minimum day index when she will have *k* gadgets. Nura always pays with burles, which are converted according to the exchange rate of the purchase day. Nura can't buy dollars or pounds, she always stores only burles. Gadgets are numbered with integers from 1 to *m* in order of their appearing in input.

Input

First line contains four integers *n*, *m*, *k*, *s* (1 ≤ *n* ≤ 2·105, 1 ≤ *k* ≤ *m* ≤ 2·105, 1 ≤ *s* ≤ 109) — number of days, total number and required number of gadgets, number of burles Nura has.

Second line contains *n* integers *a**i* (1 ≤ *a**i* ≤ 106) — the cost of one dollar in burles on *i*\-th day.

Third line contains *n* integers *b**i* (1 ≤ *b**i* ≤ 106) — the cost of one pound in burles on *i*\-th day.

Each of the next *m* lines contains two integers *t**i*, *c**i* (1 ≤ *t**i* ≤ 2, 1 ≤ *c**i* ≤ 106) — type of the gadget and it's cost. For the gadgets of the first type cost is specified in dollars. For the gadgets of the second type cost is specified in pounds.

Output

If Nura can't buy *k* gadgets print the only line with the number \-1.

Otherwise the first line should contain integer *d* — the minimum day index, when Nura will have *k* gadgets. On each of the next *k* lines print two integers *q**i*, *d**i* — the number of gadget and the day gadget should be bought. All values *q**i* should be different, but the values *d**i* can coincide (so Nura can buy several gadgets at one day). The days are numbered from 1 to *n*.

In case there are multiple possible solutions, print any of them.

Examples

input

Copy

5 4 2 2
    1 2 3 2 1
    3 2 1 2 3
    1 1
    2 1
    1 2
    2 2

output

3
    1 1
    2 3

input

Copy

4 3 2 200
    69 70 71 72
    104 105 106 107
    1 1
    2 2
    1 2

output

-1

input

Copy

4 3 1 1000000000
    900000 910000 940000 990000
    990000 999000 999900 999990
    1 87654
    2 76543
    1 65432

output

-1

思路：为什么会是二分呢？  这个题首先要能想到要想判断在某一天能将k件商品买齐，那么就选从第一天到这一天美元和英镑汇率最小的两天，然后将所有商品以这两个汇率转化成burle， 求出和之后判断是否可以。但是这个题这样做n\*k复杂度肯定超时。再考虑一下，如果某一天能够将K个商品买齐，那么这一天之后的那几天也一定能买齐。所以这个分界线可以用二分求出。

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int maxn=2e5+10;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    int n, m, k;
    ll s;
    ll cost[maxn][2], ans[maxn][2];
    struct node{
    	ll co;
    	int id;
    	bool operator <(const node &tmp) const{
    		return co<tmp.co;
    	}
    }c[maxn];//用来存转化之后的价格
    
    struct node2{
    	ll r;
    	int id;
    	node2(ll _r=INF, int _id=0): r(_r), id(_id){}	
    }rateA[maxn], rateB[maxn];//汇率
    
    bool check(int t){
    	ll sum=0;
    	for(int i=1; i<=m; i++)//转化
    	{
    		if(cost[i][0]==1)
    		{
    			c[i].co=cost[i][1]*rateA[t].r;
    			c[i].id=i;
    		}	
    		else{
    			c[i].co=cost[i][1]*rateB[t].r;
    			c[i].id=i;	
    		} 
    	}
    	sort(c+1, c+1+m);
    	for(int i=1; i<=k; i++)
    	{
    		
    		sum+=c[i].co;
    		ans[i][0]=c[i].id;
    		ans[i][1]=cost[c[i].id][0]==1 ? rateA[t].id : rateB[t].id;
    	}	
    	if(sum>s)
    		return false;
    	else
    		return true;
    }
    
    int main(){
    	scanf("%d%d%d%I64d", &n, &m, &k, &s);
    	
    	for(int i=1; i<=n; i++)
    	{
    		scanf("%I64d", &rateA[i].r);
    		rateA[i].id=i;
    		if(rateA[i].r>=rateA[i-1].r)
    			rateA[i]=rateA[i-1];
    	}
    	for(int i=1; i<=n; i++)
    	{
    		scanf("%I64d", &rateB[i].r);
    		rateB[i].id=i;
    		if(rateB[i].r>=rateB[i-1].r)
    			rateB[i]=rateB[i-1];
    	}
    	
    	for(int i=1; i<=m; i++)
    	{
    		scanf("%I64d%I64d", &cost[i][0], &cost[i][1]);
    	}
    	int l=1, r=n; 
    	while(l<=r){
    		int mid=(l+r)>>1;
    		
    		if(check(mid))
    			r=mid-1;
    		else
    			l=mid+1;
    	}
    	if(l==n+1)
    		printf("-1\n");
    	else
    	{
    		check(l);	
    		printf("%d\n", max(rateA[l].id, rateB[l].id));
    		for(int i=1; i<=k; i++)
    			printf("%I64d %I64d\n", ans[i][0], ans[i][1]);
    		
    	}
    	
    	
    	
    	
    	return 0;
    }