该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

青岛市最近在推广垃圾分类。上级要求将垃圾分为 $n$ 个种类，每一种垃圾只能被放入对应的垃圾桶中。由于渣朱君掌握了新型压缩技术，他的压缩技术认为垃圾只有数量之分，没有体积大小之分。

他作为青岛市的一位居民。在他居住的社区外有 $n + 1$ 个垃圾桶，标号为 $1, 2, \cdots, n, n + 1$。

对前 $n$ 个垃圾桶，它们只能接受对应标号的垃圾，并且有一定的容量。你会得到一个长度为 $n$ 的序列 $r _ 1, \cdots, r _ n$。第 $i$ 个垃圾桶只能接受第 $i$ 类垃圾，且最多只能被放入 $r _ i$ 个。

对最后一个垃圾桶，它可以接受所有种类的垃圾，容量也是几近无限的。但是，每向这个垃圾桶放入一个垃圾，居委会会向你收取 $c$ 的费用。

这天，渣朱君的家中堆放满了垃圾。在将这些垃圾分类好后，他得到了一个长度为 $n$ 的序列 $a _ 1, \cdots, a _ n$，代表第 $i$ 类垃圾有 $a _ i$ 个。

请聪明的你帮他算算，如果想要扔掉所有的这些垃圾，他的最小花费是多少。

输入格式

共三行。

第一行两个整数 $n, c$，代表垃圾的种类数和向最后一个垃圾桶放入垃圾的费用。

第二行 $n$ 个整数 $r _ 1, \cdots, r _ n$，代表垃圾桶的容量。

第三行 $n$ 个整数 $a _ 1, \cdots, a _ n$，代表每一类垃圾的数量。

输出格式

一行一个整数，代表最小花费。

2 7
4 3
7 9

63

2 10000
100 100
3 7

0

提示

样例解释

样例组 #1：最优情况下，他需要向最后一个垃圾桶中放入 $9$ 个垃圾，费用为 $7 \times 9 = 63$。

样例组 #2：最优情况下，他不需要向最后一个垃圾桶中放入任何垃圾，费用为 $0$。

数据规模与约定

对前 $20\%$ 的数据，保证 $n = 2$。

对前 $60\%$ 的数据，保证 $n, a _ i, c \leq 10 ^ 3$。

对另外 $10\%$ 的数据，保证 $c = 0$。

对另外 $10\%$ 的数据，保证 $r _ i \geq a _ i$。

对 $100\%$ 的数据，保证 $2 \leq n \leq 10 ^ 6, 0 \leq r _ i, a _ i, c \leq 10 ^ 6$。