6745. 打怪游戏 II (Monster Game II)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 你正在玩一个共有 $n$ 个关卡的游戏。每个关卡都有一只怪物。在第 $1, 2, \dots, n-1$ 关，你可以选择击杀或者避开怪物。然而，在最后一关（第 $n$ 关），你必须击杀最终的怪物才能赢得整个游戏。 击杀一只怪物需要花费 $s \cdot f$ 的时间，其中 $s$ 是该怪物的强度，而 $f$ 是你当前的技巧因子。击杀一只怪物后，你将获得一个新的技巧因子（技巧因子越低越好）。 问赢得游戏所需的最小总时间是多少？ *(注：相比第 I 代，本题不再保证怪物的强度单调递增，也不再保证新获取的技巧因子单调递减。)* ## 输入格式 第一行包含两个整数 $n$ 和 $x$，分别表示关卡数量和你的初始技巧因子。 第二行包含 $n$ 个整数 $s\_1, s\_2, \dots, s\_n$，依次表示每只怪物的强度。 第三行包含 $n$ 个整数 $f\_1, f\_2, \dots, f\_n$，依次表示击杀对应怪物后你可以获得的新技巧因子。 ## 输出格式 输出一个整数，表示赢得游戏所需的最小总时间。 ## 输入输出样例 ### 输入 #1 ``` 5 100 50 20 30 90 30 60 20 20 10 90 ``` ### 输出 #1 ``` 2600 ``` ### 样例解释 最优的策略是击杀第 $2$ 只和第 $5$ 只怪物： * 第 2 只：花费时间 $s\_2 \cdot x = 20 \cdot 100 = 2000$。技巧因子变更为 $f\_2 = 20$。 * 第 5 只：花费时间 $s\_5 \cdot f\_2 = 30 \cdot 20 = 600$。 总时间为 $2000 + 600 = 2600$。 ## 说明/提示 ### 数据规模与约定 * $1 \le n \le 2 \cdot 10^5$ * $1 \le x \le 10^6$ * $1 \le s\_i, f\_i \le 10^6$