3976. 运送粮食

【题目背景】

不要看错了哦，我是 Farmer Jorn 不是 Farmer John。

【题目描述】

Farmer Jorn 运送玉米的工具只有小推车，玉米的总重量为 $w$ 。

Farmer Jorn 有 $n$ 个小推车，它们的编号分别为 $1 \sim n$，第 $i$ 个小推车的最大承重量为 $c_i$ 。

Farmer Jorn 可以进行若干次运送，每次可以使用多辆小推车。但在宇宙射线伽马值 $k$ 的影响下，小推车总是莫名其妙地出故障。

第 $i$ 次运送时，Farmer Jorn 只能选择 小车编号 $\bmod$ $k$ 等于 当前运送次数 $\bmod$ $k$ 的小推车。

注意：$\bmod$ 是取余运算， $a \bmod b$ 的结果是 $a\%b$ 的结果。

问：Farmer Jorn 最少要用多少次才能运送完玉米？

【输入格式】

第一行两个正整数 $n, k, w$，意义见【题目描述】。

第二行 $n$ 个整数 $c_1, \cdots, c_n$，分别表示每辆小推车的最大承重量。

【输出格式】

一行一个整数，表示 Farmer Jorn 运送完玉米的最小次数。

【样例1输入】

5 2 23
2 1 2 1 1

【样例1输出】

7

【样例1说明】

这是一个 $k=2$ 的情况，总重 $23$ 的玉米堆。

第 $1$ 次运输时，$1 \bmod 2 =1$，我们可以选择有相同余数编号的小车 $1$号、$3$号、$5$号共计运输 $5$ 单位重量玉米堆，剩余 $17$ 单位重量。

第 $2$ 次运输时，$2\bmod 2=0$，我们可以选择有相同余数编号的小车 $2$号，$4$号共计运输 $2$ 单位重量玉米堆，剩余$15$单位重量。

第 $3$ 次运输时，$3 \bmod 2 =1$，我们可以选择有相同余数编号的小车 $1$号、$3$号、$5$号共计运输 $5$ 单位重量玉米堆，剩余 $10$ 单位重量。

第 $4$ 次运输时，$4\bmod 2=0$，我们可以选择有相同余数编号的小车 $2$号，$4$号共计运输 $2$ 单位重量玉米堆，剩余$8$单位重量。

第 $5$ 次运输时，$5 \bmod 2 =1$，我们可以选择有相同余数编号的小车 $1$号、$3$号、$5$号共计运输 $5$ 单位重量玉米堆，剩余 $3$ 单位重量。

第 $6$ 次运输时，$6\bmod 2=0$，我们可以选择有相同余数编号的小车 $2$号，$4$号共计运输 $2$ 单位重量玉米堆，剩余$1$单位重量。

第$7$次运输完毕,不再解释。

【样例2输入】

10 5 1000
2 5 6 1 5 6 9 7 7 1

【样例2输出】

102

【数据规模与约定】

对于 $40 \%$ 的数据，$1 \le n, k, c_i, w \le 10^3$。

对于另外 $40 \%$ 的数据，$k=2$。

对于 $100\%$ 的数据，$1\le n, k\le 10^6$，$1\le c_i\le w\le 10^9$。

【来源】

2024年校际联合邀请赛 普及组-第2场 Task1