链接: https://cses.fi/problemset/task/2084

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你在玩一个包含 $n$ 个关卡的游戏，每个关卡都有一只怪物。在关卡 $1,2,\dots,n-1$ 中，你可以选择击杀或躲避怪物；但在第 $n$ 关，你必须击杀最终的怪物才能通关。

击杀一只怪物需要 $sf$ 的时间，其中 $s$ 是怪物的强度，$f$ 是你的技巧值（技巧值越小越好）。击杀一只怪物后，你会获得一个新的技巧值。你通关游戏所需的最短时间是多少？

输入

第一行有两个整数 $n$ 和 $x$：关卡数量与你初始的技巧值。

第二行有 $n$ 个整数 $s_1,s_2,\dots,s_n$：每只怪物的强度。

第三行有 $n$ 个整数 $f_1,f_2,\dots,f_n$：击杀怪物后你的新技巧值。

输出

输出一个整数：通关游戏的最短时间。

数据范围

$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$

样例输入

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

样例输出

4800