CSES2084 怪物游戏 I
#CS2084. 怪物游戏 I
怪物游戏 I
题目背景
翻译自 CSES-2084 题。
题目描述
你正在玩一个包含 n 个关卡的游戏。每个关卡都有一个怪物。在第 1,2,...,n−11, 2, ..., n-11,2,...,n−1 关，你可以选择击杀怪物或逃避怪物。然而，在第 n 关，你必须击杀最后一个怪物才能赢得游戏。
击杀怪物需要的时间是 s×fs \times fs×f，其中 s 是怪物的强度，f 是你的技能系数（技能系数越低越好）。击杀怪物后，你会得到一个新的技能系数。请你计算赢得游戏的最小总时间。
输入格式
第一行输入两个整数 n 和 x，分别表示关卡的数量和你的初始技能系数。
第二行输入 n 个整数 s1,s2,...,sns_1, s_2, ..., s_ns1,s2,...,sn，表示每个怪物的强度。
第三行输入 n 个整数 f1,f2,...,fnf_1, f_2, ..., f_nf1,f2,...,fn，表示击杀怪物后你获得的新技能系数。
输出格式
输出一个整数：表示赢得游戏的最小总时间。
样例
5 100
20 30 30 50 90
90 60 20 20 10
4800
样例1解释 最好的打法是杀死第三个和第五个怪物。
说明/提示
1≤s1≤s2≤...≤sn≤1061 \leq s_1 \leq s_2 \leq ... \leq s_n \leq 10^61≤s1≤s2≤...≤sn≤106；
x≥f1≥f2≥...≥fn≥1x \geq f_1 \geq f_2 \geq ... \geq f_n \geq 1x≥f1≥f2≥...≥fn≥1。