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