终结技

题目内容

仁人鱼正在玩杀雕尖塔，他正在面对一个强大的敌人，敌人仅需一回合就能解决掉仁人鱼，但是好在仁人鱼是先手，也就是说他在第一个回合必须击败敌人。

仁人鱼手上有 $n$ 张攻击牌，$m$ 点能量，这 $n$ 张攻击牌中有一张是终结技，其效果是造成打出攻击牌个数乘以 $k$ 的伤害（打出攻击牌的个数不包括此牌）。前 $n-1$ 张牌为普通的攻击牌，第 $i$ 张耗能 $a_i$ ，造成 $b_i$ 点伤害，第 $n$ 张牌为终结技，耗能 $a_n$ ，仁人鱼想知道他这一回合最多能造成多少伤害。

输入描述

第一行三个数 $n,m,k$ 。

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$ 。

第三行 $n-1$ 个数，第 $i$ 个数表示 $b_i$ 。

输出描述

一行一个数，表示最多能造成的伤害。

样例输入1

3 5 5
1 1 3
3 1

样例输出1

14

样例1解释

3张牌耗能不超过5，可以全打出，前两张牌造成3+1=4点伤害，然后使用终结技，造成2*5=10点伤害，共14点

样例输入2

4 5 5
2 2 3 3
20 30 2

样例输出2

50

样例2解释

打出前两张牌，造成20+30=50点伤害

数据范围

$1 \leq n\leq 8000,\quad 1 \leq m\leq 5000,\quad 1\leq b_i,k\leq 10^9$