题目内容

精密装配线上有 $n$ 个工位，第 $i$ 个工位的节拍读数为 $a_i$。工艺标准把序列称为 $g$ 节拍均衡：每一个长度为 $g$ 的连续工位段，读数之和都必须相等。每次校准只能把某一个工位的读数加 1，且最多校准 $d$ 次。请在完成均衡后，最大化所有工位读数中的最大值；若即使用完 $d$ 次校准也无法达到均衡，输出 -1。

约束：$1 \le n,d \le 10^5$，$1 \le g \le n$，$-1000000000 \le a_i \le 1000000000$。

输入描述

第一行三个整数 $n$、$g$、$d$，分别表示工位数、节拍长度以及校准次数上限。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各工位读数。 保证 $1 \le n,d \le 10^5$，$1 \le g \le n$，$-1000000000 \le a_i \le 1000000000$。