codeforces 609D D. Gadgets for dollars and pounds(二分+贪心)

题目链接：

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 ai (1 ≤ ai ≤ 106) — the cost of one dollar in burles on i-th day.

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

Each of the next m lines contains two integers ti, ci (1 ≤ ti ≤ 2, 1 ≤ ci ≤ 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 qi, di — the number of gadget and the day gadget should be bought. All values qi should be different, but the valuesdi 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

output

3
1 1
2 3

input

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

output

-1

input

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

output

-1


题意：

给了n天时间,每天的美元和英镑兑换这种货币的汇率,然后给了m种商品和s个这种货币,问买k种商品最少需要多少天;而且商品只能按美元或者英镑来买;


思路：

二分最少的天数,然后贪心要买的k件商品,(提前分好类和计算好前x个需要的英镑或者美元数),暴力枚举1类型和2类型的各多少个,换算成这种货币后看是否能买下来;
还有就是找到最小天数后再找一遍1类型和2类型多少个,在哪天买的自然是在汇率最小的那一天买啊;


AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+4;
typedef long long ll;
int n,m,k,s,ma[N],mb[N],ans,a[N],b[N],type,co;
ll suma[N],sumb[N];
struct node
{
    friend bool operator< (node x,node y)
    {
        return x.num<y.num;
    }
    int num,pos;
};
node fa[N],fb[N];
int cnta=1,cntb=1;
int check(int x)
{
    ll sum=0;
    for(int i=0;i<cnta&&i<=k;i++)
    {
        if(k < i+cntb)
        {
            sum = suma[i]*(ll)a[ma[x]]+sumb[k-i]*(ll)b[mb[x]];//按汇率最少的时候算需要多少这种货币;
            if(sum <= s)return 0;
        }
    }
    return 1;
}
int bi()
{
    int l = 1,r = n,mid;
    while(l <= r)
    {
        mid = (l+r)>>1;
        if(check(mid))l = mid+1;//return 1表示全都不符合天数需要往后才能找到更小的汇率;
        else r = mid-1;
    }
    return l;//l-1表示的是最后一个不满足的天数,那么l天就是第一个满足的天数,也是最小的;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&s);
    a[0] = 1e6+1,b[0] = 1e6+1;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        if(a[ma[i-1]] > a[i])ma[i] = i;//ma[i]记录的是前i天美元汇率最小的那天;mb[i]也是;
        else ma[i] = ma[i-1];
    }
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&b[i]);
        if(b[mb[i-1]] > b[i])mb[i] = i;
        else mb[i] = mb[i-1];
    }
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d",&type,&co);
        if(type==1)//分类
        {
            fa[cnta].num = co;
            fa[cnta].pos = i;
            cnta++;
        }
        else
        {
            fb[cntb].num = co;
            fb[cntb].pos = i;
            cntb++;
        }
    }
    sort(fa+1,fa+cnta);//分类后排序,方便后面贪心;
    sort(fb+1,fb+cntb);
    suma[0] = 0;
    sumb[0] = 0;
    for(int i = 1;i < cnta;i++)
    {
        suma[i] = suma[i-1]+(ll)fa[i].num;//suma[i]表示前i个需要美元买的商品一共需要多少美元;
    }
    for(int i = 1;i < cntb;i++)
    {
        sumb[i] = sumb[i-1]+(ll)fb[i].num;
    }
    int fs = bi();
    if(fs > n)printf("-1
");
    else
    {
        printf("%d
",fs);
        ll sum=0;
        for(int i=0;i<cnta&&i<=k;i++)
        {
            if(k < i+cntb)
            {
                sum = suma[i]*(ll)a[ma[fs]]+sumb[k-i]*(ll)b[mb[fs]];
                if(sum <= s)
                {
                    ans = i;
                    break;
                }
            }
        }
        for(int i=1;i<=ans;i++)
        {
            printf("%d %d
",fa[i].pos,ma[fs]);
        }
        for(int i=1;i<=k-ans;i++)
        {
            printf("%d %d
",fb[i].pos,mb[fs]);
        }
    }
    return 0;
}