CF609D.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.

努拉想购买 $k$ 个电子设备。她仅有 $s$ 卢布（burles）可用于此目的。每个设备只能以美元或英镑购买，即每个设备仅以某一种货币标价，且其货币类型与对应价格均保持不变。

努拉可以在 $n$ 天内购买设备。对于每一天，已知美元和英镑的汇率，因此可知当天将卢布兑换为美元或英镑的成本。

每一天（从第 $1$ 天到第 $n$ 天），努拉均可按当日汇率购买若干设备。每天她可自由选择购买任意设备，但每个设备在整个 $n$ 天内最多只能被购买一次。

请帮助努拉找出她能凑齐 $k$ 个设备的最早天数（即最小的天数索引）。努拉始终使用卢布付款，而卢布按购买当日的汇率兑换为对应货币。努拉不能预先购买美元或英镑，她手中始终只持有卢布。设备按其在输入中出现的顺序编号为 $1$ 到 $m$。

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.

第一行包含四个整数 $n$、$m$、$k$、$s$（$1 ≤ n ≤ 2·10^5$，$1 ≤ k ≤ m ≤ 2·10^5$，$1 ≤ s ≤ 10^9$）——分别表示天数、小工具总数、所需小工具数量，以及努拉拥有的 burles 数量。

第二行包含 $n$ 个整数 $a_i$（$1 ≤ a_i ≤ 10^6$）——第 $i$ 天 1 美元兑换的 burles 数。

第三行包含 $n$ 个整数 $b_i$（$1 ≤ b_i ≤ 10^6$）——第 $i$ 天 1 英镑兑换的 burles 数。

接下来的 $m$ 行中，每行包含两个整数 $t_i$、$c_i$（$1 ≤ t_i ≤ 2$，$1 ≤ c_i ≤ 10^6$）——小工具的类型及其价格。第一类小工具的价格以美元计；第二类小工具的价格以英镑计。

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.

如果努拉无法购买 $k$ 个电子设备，则仅输出一行数字 $-1$。

否则，第一行应包含一个整数 $d$ —— 努拉获得 $k$ 个电子设备的最早天数（即最小的天数编号）。接下来的 $k$ 行中，每行输出两个整数 $q_i,\,d_i$ —— 分别表示第 $i$ 个电子设备的编号及其购买日期。所有 $q_i$ 的值必须互不相同，但 $d_i$ 的值可以重复（即努拉可以在同一天购买多个电子设备）。天数编号从 $1$ 到 $n$。

若存在多种可能的解，输出任意一种即可。