유명한 아티스트 Karuna는 리듬 게임을 하고 있습니다.

Karuna는 노래의 노트들을 맞추려고 합니다. 노래는 $N$개의 노트로 이루어진 수열입니다.

이 게임에서 사용되는 점수 시스템은 다음과 같습니다:

• 노래가 시작할 때 (첫 번째 노트 전), 점수는 0점이고 콤보 보너스도 0입니다.
• 각 노트는 고유한 값을 가집니다. $i$번째 노트의 값은 $A_i$입니다.
• 콤보 보너스 값은 Karuna가 현재 노트를 놓치면 0이고, Karuna가 이 노트를 맞추고 연속으로 맞춘 노트의 개수가 $j$개라면 $C_j$입니다.
• Karuna가 $i$번째 노트를 맞추고 그 직후의 콤보 길이가 $j$가 된다면, 점수에 $A_i \cdot C_j$가 더해집니다.
• Karuna가 노트를 놓치면 콤보 길이는 0으로 초기화됩니다. 만약 놓치기 전의 콤보 길이가 0이 아니었다면 (즉, 바로 이전 노트를 맞추었다면), 콤보 종료 점수 $P$가 점수에 더해집니다.
• Karuna가 노래의 마지막 노트를 맞춘 경우에도 콤보 종료 점수 $P$가 점수에 더해집니다.

Karuna의 실력으로는 노래를 연주하는 동안 최대 $K$개의 노트만 맞출 수 있습니다. 각 노트에 대해, Karuna는 총 맞춘 노트의 개수가 $K$개 이하인 한, 노트를 맞추거나 놓치기로 선택할 수 있습니다.

모든 매개변수가 주어졌을 때, Karuna가 얻을 수 있는 최대 점수를 구하세요.

입력

첫 번째 줄에 노래의 노트 수 $N$, Karuna가 맞출 수 있는 최대 노트 수 $K$, 콤보 종료 점수 $P$가 공백으로 구분되어 주어집니다 ($1 \le N, K \le 2000$, $-10^9 \le P \le 10^9$).

두 번째 줄에 $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가 리듬 게임에서 얻을 수 있는 최대 점수를 나타내는 정수 하나를 출력합니다.

예제

입력 1

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

출력 1

57