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