Monster Game I

题目描述

你正在玩一个有 n 个关卡的游戏。每个关卡有一个怪物。在关卡 1,2,\dots,n-1 上，你可以选择杀死或逃跑该怪物。然而，在关卡 n 上你必须杀死最终的怪物才能赢得游戏。 杀死一个怪物需要 $s f$ 时间，其中 $s$ 是怪物的强度，$f$ 是你的技能系数（技能系数越低越好）。在杀死一个怪物后，你会得到一个新的技能系数。问你以最短的总时间赢得游戏是多少？

输入格式

第一行包含两个整数 n 和 x：关卡数和你的初始技能系数。 第二行包含 n 个整数 $s_1,s_2,\dots,s_n$：每个怪物的强度。 第三行包含 n 个整数 $f_1,f_2,\dots,f_n$：在杀死某个怪物后你的新的技能系数。

输出格式

输出一个整数：赢得游戏的最短总时间。

5 100
20 30 30 50 90
90 60 20 20 10

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$ 样例解释：最优的玩法是杀死第三个和第五个怪物。

标签: CSES2084|先进技术

来源

CSES2084|先进技术