CF609D Gadgets for dollars and pounds

一个人手上有 $s$ 卢布，他要在 $n$ 天内买 $m$ 样东西中的 $k$ 样。 每个物品有两种支付方式，要么用美元，要么用英镑。 每天有不同的支付方式代价，即换取一美元或英镑，需要付出 $x_i$ 卢布的代价。 求最早完成买 $k$ 样东西的天数。如果无法完成任务，输出 `-1`。 一种商品只能购买一次，但是一天可以买多种商品。

第一行包含四个整数，$n, m, k, s$。 第二行 $n$ 个整数，表示每天多少卢布换一美元。 第三行 $n$ 个整数，表示多少卢布换一英镑。 接下来是 $m$ 行，每行 $2$ 个整数，表示每样东西用什么货币结账（ $1$ 是美元，$2$ 是英镑），以及要多少那种外币。

输出最短到第几天买完 $k$ 样商品。 以及输出 $q_i$ 与 $d_i$ 表示在第 $d_i$ 天购买第 $q_i$ 样东西。

对于所有数据 $1\le n\le 2\times 10^5,1\le k\le m\le 2\times 10^5,1\le s\le 10^9,1\le a_i\le 10^6,1\le b_i\le 10^6,1\le t_i\le 2,1\le c_i\le 10^6$。