基础最优化练习题

题目背景

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$ 满足条件。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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$。