题目描述

著名艺人 Karuna 正在玩一款节奏游戏。歌曲中共有 $N$ 个音符，Karuna 可以选择击中或错过每个音符。

游戏的计分规则如下：

• 歌曲开始前，分数为 $0$，连击长度为 $0$；
• 第 $i$ 个音符有基础值 $A_i$；
• 如果当前音符被错过，则连击长度变为 $0$；
• 如果当前音符被击中，并且击中后连续击中的音符数量为 $j$，则本次获得分数

• 如果某个音符被错过，且在它之前的连击长度非零，则额外获得一次连击结束奖励 $P$；
• 如果最后一个音符被击中，则歌曲结束时也会额外获得一次连击结束奖励 $P$。

Karuna 的能力有限，整首歌中最多只能击中 $K$ 个音符。对于每个音符，他可以自由选择击中或错过，只要总击中数量不超过 $K$。

给定所有参数，请计算 Karuna 能获得的最大分数。

输入格式

第一行包含三个整数 $N,K,P$，分别表示音符数量、最多能击中的音符数量，以及连击结束奖励。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，其中 $A_i$ 表示击中第 $i$ 个音符的基础值。

第三行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$，其中 $C_j$ 表示连击长度为 $j$ 时的倍率。

输出格式

输出一个整数，表示 Karuna 在这款节奏游戏中能够获得的最大分数。

数据范围

• $1\le N,K\le 2000$；
• $-10^9\le P\le 10^9$；
• $0\le A_i\le 10^5$；
• $-10^5\le C_j\le 10^5$；
• 对所有 $1\le j\le N-1$，保证 $C_j\ge C_{j+1}$。

样例 1

输入

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

输出

57