解题思路

先把每个时刻真正还缺多少容量算出来。设

$need_i = \max(0, a_i - b_i)$

那么问题就变成：

• 每次启动一个扩容包，会在一段长度为 $w$ 的连续区间内，每个时刻都额外提供 $x$ 容量；

题目内容

多多最近在做一条服务链路的大促扩容预案。他拿到了未来$n$个时间点的负载预测。 第$i$个时间点

• 业务需求为$a_i$;
• 当前基础容量为$b_i$

多多最多可以申请$m$个“临时扩容包”。每个扩容包都有相同的扩容量$x$。如果一个扩容包在第$i$个时间点启动，那么它会在从$i$开始的长度为$w$的时间区间，即时间点$i,i+1,...,i+w-1$上各额外提供容量，若区间超过第$n$个时间点，超出的部分无需考虑。多个扩容包可以在同一时刻启动，它们的效果也可以叠加。

请你求出最小的非负整数$x$，使得可以通过在启动不超过$m$个扩容包的情况下，让所有时间点都满足：基础容量+所有生效中的扩容包容量>=业务需求。

在得到最小可行的$x$之后，多多还想知道：在这个最小$x$下，最少需要启动多少个扩容包。如果无论怎样都无法满足全部时间点的业务需求，输出$-1$。

输入描述

第一行输入一个整数$T$，表示测试数据组数。

接下来对每组数据:

• 第一行输入$3$个整数$n,m,w$;

• 第二行输入$n$个整数$a_1，a_2,...,a_n$，表示各时间点的业务需求;

• 第三行输入$n$个整数$b_1，b_2,...,b_n$，表示各时间点的基础容量

输出描述

对每组数据各输出一行:

• 若存在可行解，输出两个整数$x,C$，分别表示最小可行的单包扩容量，以及在该扩容量下最少需要启动的扩容包数量
• 若不存在可行解则输出-1

补充说明

$1≤T≤3$

$1≤n≤10^6$

$0≤m≤10^6$

$1≤w≤n$

$0≤a_i,b_i≤10^9$

单个测试用例中所有测试数据的$n$之和不超过$10^6$

样例1

输入

2
5 2 3
5 7 6 4 5
4 4 4 4 4
6 2 2
10 1 10 1 10 1
0 0 0 0 0 0 

输出

3 2
-1

样例1

输入

3
1 1 1
5 
2
3 4 3
13 13 13
1 1 1
5 1 4
0 0 0 0 6
0 0 0 0 0 

输出

3 1 
3 4
6 1