该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

程老师带着学生做跳格训练。训练场上一排格子编号从 $0$ 到 $n$，他站在 $0$ 号格，目标是恰好到达 $n$ 号格。每次跳跃，他可以从当前格 $pos$ 跳到 $pos + L$（$L$ 是跳跃长度，$1 \le L \le k$），不能越过 $n$ 号格。

每个格子 $i$（$1 \le i \le n$）上写有一个积分 $v_i$，落到该格就获得 $v_i$ 分，积分可以为负。此外训练还有一条"节奏奖励"规则：若本次跳跃的长度与上一次跳跃的长度相同，额外获得 $b$ 分；连续多步保持同一长度，则每步都可获得该奖励。第一次跳跃没有上一次，不获得奖励。

程老师想知道：到达 $n$ 号格最多能获得多少总积分？

输入格式

从文件 jump.in 中读入数据。

第一行三个正整数 $n, k, b$，分别表示格子数（编号 $0$ 到 $n$）、每次跳跃长度上限和节奏奖励分值。

第二行 $n$ 个整数 $v_1, v_2, \dots, v_n$，相邻两个整数之间用一个空格隔开。

输出格式

输出到文件 jump.out 中。

一行一个整数，表示能获得的最大总积分。

数据范围

对于所有测试数据，保证：$1 \le n \le 10^5$，$1 \le k \le 300$，$1 \le b \le 10^5$，$|v_i| \le 10^4$。

特殊性质 A：所有格子上的积分都不大于 $0$。

特殊性质 B：$k = n$（即允许从 $0$ 号格一步跳到 $n$ 号格）。

5 2 3
1 2 -5 4 2

16

4 2 5
3 -1 -1 3

19

样例解释

样例 1：最优路线是 0→1→2→3→4→5，每步跳 1 格，落格积分 $1 + 2 - 5 + 4 + 2 = 4$；第 2 至第 5 次跳跃的长度都与上一次相同，共得 $4 \times 3 = 12$ 分节奏奖励，总计 $16$ 分。若改走 0→2→4→5，落格积分 $2 + 4 + 2 = 8$，只有 1 次奖励得 $3$ 分，总计 $11$ 分，不如前者。

样例 2：最优路线是 0→1→2→3→4，每步跳 1 格，落格积分 $3 - 1 - 1 + 3 = 4$，后三步各得 $5$ 分奖励，共 $15$ 分，总计 $19$ 分。