音乐游戏 - Problem

著名的艺术家 Karuna 正在玩一款节奏游戏。

他正尝试击中一首歌曲中的音符。这首歌曲由 $N$ 个音符组成的序列构成。

该游戏使用的计分系统如下：

在歌曲开始时（在第一个音符之前），得分为 $0$，连击奖励为 $0$。
每个音符都有自己的分值。第 $i$ 个音符的分值为 $A_i$。
如果 Karuna 未击中当前音符，则连击奖励值等于 $0$；如果 Karuna 击中了当前音符，且此时他连续击中了 $j$ 个音符，则连击奖励值为 $C_j$。
如果 Karuna 击中了第 $i$ 个音符，且击中后的连击长度为 $j$，则将 $A_i \cdot C_j$ 的值累加到得分中。
如果 Karuna 未击中某个音符，连击长度将重置为 $0$。如果在此之前连击长度不为 $0$（换句话说，如果 Karuna 击中了上一个音符），则将连击结束得分 $P$ 累加到得分中。
如果 Karuna 击中了歌曲中的最后一个音符，连击结束得分 $P$ 也会被累加到得分中。

Karuna 的技术允许他在整首歌曲中最多击中 $K$ 个音符。对于每个音符，他可以选择击中或未击中，只要他总共击中的音符数不超过 $K$ 即可。

给出所有参数，求 Karuna 可以获得的最高得分。

第一行包含三个整数 $N, K$ 和 $P$（$1 \le N, K \le 2000$，$-10^9 \le P \le 10^9$），分别表示歌曲中的音符数量、Karuna 最多可以击中的音符数量以及连击结束得分。

第二行包含 $N$ 个由空格隔开的整数。第 $i$ 个整数表示击中第 $i$ 个音符的分值 $A_i$（$0 \le A_i \le 10^5$）。

第三行包含 $N$ 个由空格隔开的整数。第 $j$ 个整数表示连击长度为 $j$ 时的得分 $C_j$（$-10^5 \le C_j \le 10^5$，且对于所有 $1 \le j \le N - 1$，保证 $C_j \ge C_{j+1}$）。

输出一个整数，表示 Karuna 在该节奏游戏中能获得的最高得分。

5 5 1
5 4 3 2 1
5 4 3 2 1

QOJ.ac