题目内容

矿场钻机手按班表下井。掌子面有 q 块待破的矿岩，硬度按长度为 $c$ 的序列 $h_1,h_2,\ldots,h_c$ 逐日循环：第 1 天硬度为 $h_1$，第 2 天为 $h_2$，第 $c$ 天为 $h_c$，第 $c+1$ 天又回到 $h_1$。钻机初始功率为 $w$。台账规定功率按周期抬升：第 $D$ 天的功率等于 $w+\lfloor(D-1)/c\rfloor$，也就是每过完整的 $c$ 天，功率加 1。

每个工作日最多处理一块矿岩：若当天功率不小于当天硬度，就打掉一块，剩余块数减 1；否则空锤，矿岩块数不变。下一天硬度仍按循环重新取值。所有矿岩硬度变化相同，打哪一块没有区别。

请计算打掉全部 q 块矿岩所需的最少天数。保证一定能打完。

约束：

• 1 $\le$ $c$ $\le$ 200000
• 1 $\le$ $q$ $\le$ 1000000000000
• 0 $\le$ $w$ $\le$ 1000000000000
• 1 $\le$ $h_i$ $\le$ 1000000000000

输入描述

第一行三个整数 $c$、$q$、$w$（1 $\le$ $c$ $\le$ 200000，1 $\le$ $q$ $\le$ 1000000000000，0 $\le$ $w$ $\le$ 1000000000000），依次表示硬度周期长度、矿岩块数和初始功率。

第二行 $c$ 个整数 $h_1,h_2,\ldots,h_c$（1 $\le$ $h_i$ $\le$ 1000000000000），表示一个周期内每天的硬度。

输出描述

输出一个整数，表示打完所有矿岩的最少天数。

样例1

输入

4 3 2
4 1 8 3

输出

8

说明

• 第 2 天功率 2 $\ge$ 硬度 1，打掉第 1 块。
• 第 6 天功率 3 $\ge$ 硬度 1，打掉第 2 块。
• 第 8 天功率 3 $\ge$ 硬度 3，打掉第 3 块。
• 共 8 天。

样例2

输入

2 5 0
3 9

输出

15

说明

功率每 2 天加 1。能打掉矿岩的日子是第 7、9、11、13、15 天（当天硬度为 3 且功率已经够），打满 5 块最少需要 15 天。

样例3

输入

1 1 0
1

输出

2

说明

第 1 天功率 0 小于硬度 1，空锤；第 2 天功率变为 1，打掉唯一一块，答案为 2。