Problem Description

Xiao I has $n$ factories located along the route from place $A$ to place $B$. The distance from $A$ to the $i$-th factory is $a_i$ kilometers. The processing plant is at place $B$, which is $x$ kilometers away from $A$. Xiao I needs to transport the goods from these factories to the processing plant at $B$.

However, there was a heavy rainstorm today, and the goods in the warehouses got damp. For each item of goods, for every $1$ minute it is stored in a warehouse or in Xiao I's backpack, its value decreases by $m$ yuan. It is known that tonight each factory will produce $b_i$ items of goods, and it is also known how many minutes after the rainstorm begins each item will be produced.

Xiao I's initial stamina is $c$, and his speed is $1$ kilometer per minute. But every time he walks $1$ kilometer, he loses $1$ stamina point (when stamina is $0$, walking is not allowed). Each time he sets out, Xiao I must go from $A$ to $B$, and then return from $B$ to $A$. He only takes away all goods that have been produced in the warehouses of the factories along the way when traveling from $A$ to $B$. After he arrives at $A$, he can immediately set out again. In particular, he may set out at a negative time. Assume his backpack has infinite capacity, and the weight of goods does not affect stamina consumption.

To reduce the loss, Xiao I built a clone-making device. This machine can create infinitely many clones of him, but for each departure, at most one clone can be created. The clones share stamina with the original body, and strictly follow the operations described in Paragraph 3. Xiao I must ensure that at any time, the current stamina can support every existing clone (including the original) to return home at $A$.

After finishing preparations, Xiao I finds that the rainstorm has already lasted for $k$ minutes. He urgently wants to know the minimum amount of money he will lose (i.e., the decrease in value of the goods), and he asks you for help to provide a plan.

Input Format

This problem has multiple sets of testdata within a single test point.

The first line contains an integer $t$, the number of test cases.

Then, for each test case:

The first line contains five integers $n,m,x,c,k$.

The next line contains $n$ integers $a_1\sim a_n$.

The next line contains $n$ integers $b_1\sim b_n$.

The next $n$ lines: the $i$-th line contains $b_i$ integers, indicating that the goods in factory $i$ are produced $t_{i,j}$ minutes after the rainstorm begins.

Output Format

For each test case:

If it is impossible for Xiao I to transport all goods to the processing plant and return home, output a single line containing -1.

Otherwise, output an integer on the first line, the minimum amount of money Xiao I will lose.

Then output several lines, each line containing two numbers. For the $i$-th such line:

• The first number is the departure time of Xiao I's $i$-th trip (measured from when he asked you for help). It must be output in increasing order, and the time may be negative.

• The second number indicates whether a new clone needs to be created for this trip. If yes, output $1$, otherwise output $0$.

If a solution exists, after finishing the output of the plan, output a line -1 -1 to indicate the end of the plan.

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

Hint

[Sample Explanation]

For the first test case of sample $3$:

Xiao I asks you for help $1$ minute after the rainstorm begins. The plan you provide is: at $3$ minutes after the rainstorm begins, Xiao I leaves home, reaches warehouse $1$ at $4$ minutes, reaches place $B$ at $5$ minutes, returns home at $7$ minutes, and the loss is $3$ yuan.

[Constraints]

For all testdata, it is guaranteed that $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$.

The input size of this problem is large. Please use a fast input method.

The statement of this problem has been updated. Original statement during the contest.

Translated by ChatGPT 5