背景

YSGH is our red sun.

题目描述

YSGH 有一个数 $x$，初值为 $0$。接下来 $n$ 分钟，每分钟 YSGH 可以给 $x$ 加上整数 $y$，其中 $y \in [-k, k]$，同时 YSGH 需要保证第 $i$ 分钟结束时 $x \le a_i$。

设 $b_i$ 为第 $i$ 分钟结束时 $x$ 的值，现在 YSGH 给你一个 $n$ 个数的序列 $w$，你需要最大化 $\displaystyle \sum_{i = 1}^{n} b_i w_i$。

你只需要输出最大值即可。

输入格式

第一行两个正整数 $n, k$，意义同题面描述。

第二行共 $n$ 个整数，第 $i$ 个表示 $a_i$，意义同题面描述。

第三行共 $n$ 个整数，第 $i$ 个表示 $w_i$，意义同题面描述。

保证输入数据使得至少存在一个序列 $b$ 满足条件。

输出格式

第一行一个整数，表示答案。

5 1
4 3 2 3 2
5 7 -5 9 -10

24

提示

对于 $10\%$ 的数据，$n \le 10$，$k \le 1$。
对于 $20\%$ 的数据，$n \le 100$。
对于 $30\%$ 的数据，$n \le {10}^3$。
对于 $50\%$ 的数据，$n \le {10}^4$。
另有 $10\%$ 的数据，$w_i \ge 0$。
对于 $100\%$ 的数据，$1 \le n \le {10}^6$，$-{10}^6 \le w_i \le {10}^6$，$0 \le a_i \le {10}^8$，$1 \le k \le 100$。