F. Rhythm Game
time limit per test
2 с
memory limit per test
256 МБ
input
standard input
output
standard output

The famous artist Karuna is playing the rhythm gane.

The artist is trying to hit the notes in a song. The song is a sequence of $$$N$$$ notes.

The scoring system used in this game is as follows:

  • At beginning of the song (before first note), the score is $$$0$$$ and combo bonus is $$$0$$$.
  • Each note has its own cost. The cost of $$$i$$$-th note is $$$A_i$$$.
  • The combo bonus value is equal to $$$0$$$ if Karuna misses current note, or $$$C_j$$$ if Karuna hits this note and there are $$$j$$$ notes in a row which Karuna hits.
  • If Karuna hits the $$$i$$$-th note and the combo length after that is $$$j$$$, the value of $$$A_i \cdot C_j$$$ is added to the score.
  • If Karuna misses the note, the length of the combo is reset to $$$0$$$. If it was non-zero before (in other words, if Karuna hit the previous note), then the combo ending score $$$P$$$ is added to the score.
  • If Karuna hits the last note in the song, the combo ending score $$$P$$$ is added to the score as well.

Karuna's skills allow him to hit no more than $$$K$$$ notes during the song. For every note, he may choose to hit it or to miss it, as long as he hits no more than $$$K$$$ notes in total.

Given all the parameters, tell the maximum score Karuna can get.

Input

The first line of the input contains three integers $$$N$$$, $$$K$$$ and $$$P$$$ ($$$1 \le N, K \le 2000$$$, $$$-10^9 \le P \le 10^9$$$): the number of notes in the song, the maximum number of notes Karuna can hit and combo break score, respectively.

The second line contains $$$N$$$ integers separated by spaces. The $$$i$$$-th number represents the score $$$A_i$$$ for hitting the $$$i$$$-th note ($$$0 \le A_i \le 10^5$$$).

The third line contains $$$N$$$ integers separated by spaces. The $$$j$$$-th number represents the score $$$C_j$$$ for a combo of length $$$j$$$ ($$$-10^5 \le C_j \le 10^5$$$, and for all $$$1 \le j \le N-1$$$, it is guaranteed that $$$C_j \ge C_{j+1}$$$).

Output

Print one integer: the maximum score Karuna can get in the Rhythm Game.

Example
Input
5 5 1
5 4 3 2 1
5 4 3 2 1
Output
57