human
Can you provide a Python code to find the minimum day index when she will have k gadgets given the following:
Solve in Python:
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·10^5, 1 ≤ k ≤ m ≤ 2·10^5, 1 ≤ s ≤ 10^9) — 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} ≤ 10^6) — the cost of one dollar in burles on i-th day.

Third line contains n integers b_{i} (1 ≤ b_{i} ≤ 10^6) — 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} ≤ 10^6) — 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...
assistant
#Here is Python code to find the minimum day index when she will have k gadgets.

from itertools import accumulate
import sys

def solve(f, g):
    n, m, k, s = [int(x) for x in f.readline().split()]
    a_price = [(int(x), i+1) for i, x in enumerate(f.readline().split())]
    b_price = [(int(x), i+1) for i, x in enumerate(f.readline().split())]

    a_gadgets = []
    b_gadgets = []
    for i, line in enumerate(f):
        t, price = [int(x) for x in line.split()]
        if t == 1:
            a_gadgets.append((price, i + 1))
        else:
            b_gadgets.append((price, i + 1))

    a_gadgets.sort()
    b_gadgets.sort()

    prefix_a = [0] + list(accumulate(gadget[0] for gadget in a_gadgets))
    prefix_b = [0] + list(accumulate(gadget[0] for gadget in b_gadgets))

    la = min(k, len(a_gadgets))
    lb = min(k, len(b_gadgets))
    min_price_for_k = [(prefix_a[i], prefix_b[k - i], i) for i in range(k-lb, la+1)]

    for i in range(1, n):
        a_price[i] = min(a_price[i], a_price[i-1])
        b_price[i] = min(b_price[i], b_price[i-1])
        
    def expence(day):
        return lambda x: a_price[day][0]*x[0] + b_price[day][0]*x[1]

    x, y = 0, n-1
    while x <= y-1:
        day = (x + y) // 2
        min_cost = min(min_price_for_k, key = expence(day))
        if expence(day)(min_cost) > s:
            x = day+1
        else:
            y = day
    min_cost = min(min_price_for_k, key = expence(x))
    if expence(x)(min_cost) > s:
        g.write('-1\n')
    else:
        g.write(str(x+1) + '\n')
        i1 = min_cost[-1]
        A, B = ' ' + str(a_price[x][1]) + '\n', ' ' + str(b_price[x][1]) + '\n'
        for i in range(i1):
            g.write(str(a_gadgets[i][1]) + A)
        for i in range(k - i1):
            g.write(str(b_gadgets[i][1]) + B)

solve(sys.stdin, sys.stdout)