D-游游的k-好数组_牛客周赛 Round 6

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

游游定义一个数组为k-好数组，当且仅当它的所有长度为 $k$ 的区间和相等。例如，数组[1,2,2,1]为3-好数组，因为两个长度为3的区间和都是5。
游游拿到了一个大小为 $n$ 的数组，每次操作可以选择一个元素加1。游游最多可以进行 $x$ 次操作，她希望不超过 $x$ 次操作后，数组变为k-好数组，且数组的最大值尽可能大。你可以帮游游求出这个最大值吗？

输入描述:

有组询问。
每组询问输入两行，第一行输入三个正整数。第二行输入个正整数，用空格隔开。



所有询问的之和保证不超过

输出描述:

对于每组询问，输出一行答案。
如果无法用不超过次操作使得数组变成k-好数组，请输出-1。
否则输出一个正整数，代表操作后数组的最大值。

示例1

输入

复制

3
4 3 1
1 2 1 1
4 2 5
1 2 3 4
5 3 1
1 100 1 1 1

输出

复制

3
4
-1

说明

第一组询问，操作一次使得数组变为[1,3,1,1]即可。（请注意，虽然可以变成[1,2,2,1]，但这样最大值是2，不是最优）
第二组询问，操作4次使得数组变为[3,4,3,4]即可。
第三组询问，显然无法操作1次使得数组变成3-好数组。