Monster Game II

题目描述

你正在玩一个由 $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
50 20 30 90 30
60 20 20 10 90

2600

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x \le 10^6$ $1 \le s_i, f_i \le 10^6$ 样例解释：最优的游戏方式是击杀第 2 个和第 5 个怪物。

标签: CSES2085|先进技术

来源

CSES2085|先进技术