← 返回题目列表

Codeforces · 1380/D

D. 狂暴和火球

中文机器翻译题面 查看原题

一排有 $$$n$$$ 战士。第 $$$i$$$ 个战士的力量为 $$$a_i$$$。所有权力都是成对不同的。

你可以施展两种类型的法术:

1. 火球:你花费 $$$x$$$ 法力并摧毁 $$$k$$$ 连续战士;
2.狂暴:你花费$$$y$$$法力,选择两个连续的战士,力量较大的战士消灭力量较小的战士。

例如,假设战士的力量为$$$[2, 3, 7, 8, 11, 5, 4]$$$,并且$$$k = 3$$$。如果您对拥有 $$$8$$$ 和 $$$11$$$ 能力的战士施放狂暴,则所得能力序列将变为 $$$[2, 3, 7, 11, 5, 4]$$$。然后,例如,如果您对具有能力 $$$[7, 11, 5]$$$ 的连续战士施放火球术,则所得能力序列将变为 $$$[2, 3, 4]$$$。

您想要将当前的战士能力序列 $$$a_1, a_2, \dots, a_n$$$ 转换为 $$$b_1, b_2, \dots, b_m$$$。计算您需要花费的最低法力值。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$)——分别是序列 $$$a$$$ 的长度和序列 $$$b$$$ 的长度。

第二行包含三个整数$$$x, k, y$$$ ($$$1 \le x, y, \le 10^9; 1 \le k \le n$$$)——分别是火球术的成本、火球术的范围和狂暴的成本。

第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。保证所有整数 $$$a_i$$$ 成对不同。

第四行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le n$$$)。保证所有整数 $$$b_i$$$ 成对不同。

输出

打印将序列 $$$a_1, a_2, \dots, a_n$$$ 转换为 $$$b_1, b_2, \dots, b_m$$$ 的最小法力值,如果不可能的话,则打印 $$$-1$$$ 。

示例

输入 #1

5 2
5 2 3
3 1 4 5 2
3 5

输出 #1

8

输入 #2

4 4
5 1 4
4 3 1 2
2 4 3 1

输出 #2

-1

输入 #3

4 4
2 1 11
1 3 2 4
1 3 2 4

输出 #3

0