题目描述

小 I 有 $n$ 个工厂，坐落在 $A$ 地到 $B$ 地，第 $i$ 个工厂距离 $A$ 地的距离为 $a_i$ 千米。加工厂位于 $B$ 地，距离 $A$ 地 $x$ 千米，小 I 要把这些工厂里的货物运送到 $B$ 地的加工厂。

但是这天下了暴雨，仓库里的货物受潮了，每份货物每在仓库中或小 I 的背包中存放 $1$ 分钟，价值就会减少 $m$ 元钱。已知今天晚上每个工厂会生产出 $b_i$ 份货物，也知道每份货物会在暴雨来临几分钟后生产出来。

小 I 的初始体力为 $c$，速度为每分钟 $1$ 千米，但是他每行走 $1$ 千米就会减少一点体力（当体力为 $0$ 时不允许行走）。每次出发小 I 都要从 $A$ 地前往 $B$ 地，再返回 $A$ 地，他只在从 $A$ 地前往 $B$ 地时会带走沿途的工厂的仓库内所有被生产出的货物。他到达 $A$ 地后可以立刻再次出发。特别的，他可以在负数时间点出发，假定他的背包是无限大的，且货物重量与体力消耗无关。

小 I 为了亏损更少，制造了一个分身制造器。这个机器可以制造无数个他的分身，但是每一次出发最多只能制造一个分身，制造的分身与本体共用体力，完全遵循第 $3$ 段所描述的操作。小 I 需要保证在任何时候，现有体力都能支持每一个分身（包括本体）返回 $A$ 地的家。

小 I 做完准备工作后，发现暴雨已经下了 $k$ 分钟了，他迫切想要知道他最少要亏损（即货物减少的价值）多少元。他不会这个问题，于是他向你求助，想让你给出一种方案。

输入格式

本题单测试点内有多组测试数据。

第一行一个整数 $t$，表示数据组数。

接下来，对于每组数据：

第一行五个整数 $n,m,x,c,k$。

接下来一行 $n$ 个整数 $a_1\sim a_n$。

接下来一行 $n$ 个整数 $b_1\sim b_n$。

接下 $n$ 行，每行 $b_i$ 个整数，表示第 $i$ 个工厂内的货物在第 $t_{i,j}$ 分钟后生产。

输出格式

对于每组数据：

若小 I 不可能将所有货物运送至加工厂并回家，输出一行一个 -1。

否则第一行一个整数，表示小 I 最少要亏损多少元。

接下来若干行，每行两个数，对于第 $i$ 行：

• 第一个数表示小 I 第 $i$ 次出发的时间（从他向你求助时计算），必须从小到大输出，时间可以为负。

• 第二个数表示这次出发是否需要制造一个新的分身，如果需要，输出 $1$，否则输出 $0$。

如果存在方案且方案输出完后，输出一行 -1 -1，表示方案结束。

1
1 2 2 5 1
1
2
3 4

6
2 0
-1 -1

1
1 1 1 5 1
1
2
3 4

0
1 0
2 1
-1 -1

4
1 1 2 5 1
1
2
3 4
1 1 4 8 2
1
2
5 8
2 2 3 9 9
1 2
2 1
3 7
5
1 1 2 8 4
1
3
1 2 3

3
2 0
-1 -1
9
5 0
-1 -1
24
-3 0
-1 -1
4
-3 0
-2 1
-1 -1

提示

【样例解释】

对于样例 $3$ 的第一组数据解释：

小 I 在暴雨来临后 $1$ 分钟向你求助，你给出的方案是在暴雨来临后 $3$ 分钟，小 I 出门，在 $4$ 分钟到达 $1$ 号仓库，在 $5$ 分钟到达 $B$ 地，在 $7$ 分钟回到家，亏损 $3$ 元。

【数据范围】

对于全部数据，保证 $1\leq t\leq 10$，$1\leq n\leq 2\times 10^5,1\leq m,k,x\leq 10^6$，$1\le a_i\le x$，$0\leq c\leq 200$，$1\leq b_i\leq 10^5$，$\sum b_i\leq 2\times 10^5$，$0\leq t_{i,j}\leq 10^6$。

本题输入量较大，请使用较快的读入方式。

本题题面已更新，赛时原题面