#CS2085. 怪物游戏 II

怪物游戏 II

题目背景

翻译自 CSES-2085 题。

题目描述

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

2600

样例1解释 最好的打法是杀死第二个和第五个怪物。

说明/提示

$1 \leq n \leq 2 \times 10^5$

$1 \leq x \leq 10^6$

1≤si,fi≤1061 \leq s_i, f_i \leq 10^61≤si​,fi​≤106。