節奏遊戲 - 题目

著名的音樂遊戲玩家 Karuna 正在玩一款節奏遊戲。

他正試圖擊中一首歌中的音符。這首歌是由 $N$ 個音符組成的序列。

此遊戲採用的計分系統如下：

在歌曲開始時（第一個音符之前），分數為 $0$，連擊獎勵也為 $0$。
每個音符都有其自身的價值。第 $i$ 個音符的價值為 $A_i$。
如果 Karuna 漏掉了當前音符，連擊獎勵值等於 $0$；如果 Karuna 擊中此音符，且此時他連續擊中了 $j$ 個音符，則連擊獎勵值為 $C_j$。
如果 Karuna 擊中第 $i$ 個音符，且擊中後的連擊長度為 $j$，則將 $A_i \cdot C_j$ 的值加到總分中。
如果 Karuna 漏掉了音符，連擊長度將重置為 $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