有名なアーティストである Karuna は、リズムゲームをプレイしています。

この曲は $N$ 個のノーツの列からなります。

このゲームの得点システムは以下の通りです。

• 曲の開始時（最初のノーツの前）は、スコアは $0$、コンボ数は $0$ です。
• 各ノーツには固有の配点があります。$i$ 番目のノーツの配点は $A_i$ です。
• Karuna が現在のノーツをミスした場合、コンボボーナスの値は $0$ になります。Karuna がこのノーツを処理し、連続で処理したノーツ数が $j$ 個になった場合、コンボボーナスの値は $C_j$ になります。
• Karuna が $i$ 番目のノーツを処理し、その直後のコンボ数が $j$ になった場合、スコアに $A_i \cdot C_j$ が加算されます。
• Karuna がノーツをミスした場合、コンボ数は $0$ にリセットされます。もしミスする前のコンボ数が $1$ 以上であった場合（すなわち、直前のノーツを処理していた場合）、スコアにコンボ終了ボーナス $P$ が加算されます。
• Karuna が曲の最後のノーツを処理した場合も、スコアにコンボ終了ボーナス $P$ が加算されます。

Karuna の実力では、曲中に最大で $K$ 個のノーツしか処理することができません。各ノーツについて、合計で処理するノーツ数が $K$ 個以下である限り、処理するかミスするかを自由に選ぶことができます。

すべてのパラメータが与えられるので、Karuna が獲得できる最大スコアを求めてください。

入力

入力は以下の形式で与えられます。

入力の最初の行には、3 つの整数 $N, K, P$ ($1 \le N, K \le 2000$, $-10^9 \le P \le 10^9$) が空白区切りで与えられます。これらはそれぞれ、曲のノーツ数、Karuna が処理できる最大ノーツ数、コンボ終了ボーナスを表します。

2 行目には、$N$ 個の整数が空白区切りで与えられます。$i$ 番目の整数は、$i$ 番目のノーツを処理したときの配点 $A_i$ ($0 \le A_i \le 10^5$) を表します。

3 行目には、$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 がリズムゲームで獲得できる最大スコアを 1 行に出力してください。

入出力例

入力 1

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

出力 1

57