← 返回题目列表

Codeforces · 609/D

D. 美元和英镑的小工具

中文机器翻译题面 查看原题

Nura 想购买 k 个小玩意。她对此只有 s burles。她可以用美元或英镑购买每件小玩意。因此,每个小工具仅以某种货币出售。货币类型和该货币的成本不会改变。

Nura 可以购买 n 天的小玩意。您每天都知道美元和英镑的汇率,因此您知道将 burles 转换为美元或英镑的成本。

每天(从 1 到 n)Nura 可以按当前汇率购买一些小玩意。每天她都可以购买任何她想要的小玩意,但每个小玩意在 n 天内只能购买一次。

帮助 Nura 找到她将拥有 k 个小工具时的最小日期索引。 Nura 始终使用 burles 付款,并根据购买当天的汇率进行换算。努拉无法购买美元或英镑,她总是只储存糖节。小工具按照其在输入中出现的顺序用从 1 到 m 的整数进行编号。

输入

第一行包含四个整数 n、m、k、s (1 ≤ n ≤ 2·105, 1 ≤ k ≤ m ≤ 2·105, 1 ≤ s ≤ 109) — 天数、总数和所需小工具数量、Nura 拥有的 burles 数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 第 i 天 1 美元的 burles 成本。

第三行包含 n 个整数 bi (1 ≤ bi ≤ 106) — 第 i 天一磅 burles 的成本。

接下来的 m 行中的每一行都包含两个整数 ti, ci (1 ≤ ti ≤ 2, 1 ≤ ci ≤ 106) — 小工具的类型及其成本。对于第一种类型的小工具,成本以美元指定。对于第二种类型的小工具,成本以磅为单位指定。

输出

如果 Nura 无法购买 k 个小工具,则打印唯一带有数字 -1 的行。

否则,第一行应包含整数 d — 当 Nura 将有 k 个小工具时的最小日期索引。在接下来的 k 行中,每一行打印两个整数 qi、di——小工具的数量和应该购买小工具的日期。所有值 qi 都应该不同,但值 di 可以重合(这样 Nura 一天可以购买多个小工具)。天数从 1 到 n。

如果有多种可能的解决方案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

3
1 1
2 3

输入 #2

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

输出 #2

-1

输入 #3

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

输出 #3

-1