基础最优化练习题

题目背景

YSGH is our red sun.

题目描述

YSGH有一个数$x$,初值为$0$。接下来$n$分钟,每分钟YSGH可以给$x$加上整数$y$,其中$y\in[-k,k]$,同时YSGH需要保证第$i$分钟结束时$x \leq a_i$。 设$b_i$为第$i$分钟结束时$x$的值,现在YSGH给你一个$n$个数的序列$w$,你需要最大化$\sum_{i=1}^{n}b_iw_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\le10,\ k<=1$ 对于20%的数据:$n\le100$ 对于30%的数据:$n\le1000$ 对于50%的数据:$n\le10000$ 另有10%的数据:$w_i\ge0$ 对于100%的数据:$n\le10^6,\ -10^6\le w_i\le10^6,\ 0\le a_i\le10^8,\ 1\le k\le100$