游游定义一个数组为k-好数组，当且仅当它的所有长度为的区间和相等。例如，数组[1,2,2,1]为3-好数组，因为两个长度为3的区间和都是5。 游游拿到了一个大小为的数组，每次操作可以选择一个元素加1。游游最多可以进行次操作，她希望不超过次操作后，数组变为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-好数组。
加载中...