Berserk And Fireball
Contest: Educational Codeforces Round 91 (Rated for Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, greedy, implementation, math, two pointers

There are $$$n$$$ warriors in a row. The power of the $$$i$$$-th warrior is $$$a_i$$$. All powers are pairwise distinct.

You have two types of spells which you may cast:

1. Fireball: you spend $$$x$$$ mana and destroy exactly $$$k$$$ consecutive warriors;
2. Berserk: you spend $$$y$$$ mana, choose two consecutive warriors, and the warrior with greater power destroys the warrior with smaller power.

For example, let the powers of warriors be $$$[2, 3, 7, 8, 11, 5, 4]$$$, and $$$k = 3$$$. If you cast Berserk on warriors with powers $$$8$$$ and $$$11$$$, the resulting sequence of powers becomes $$$[2, 3, 7, 11, 5, 4]$$$. Then, for example, if you cast Fireball on consecutive warriors with powers $$$[7, 11, 5]$$$, the resulting sequence of powers becomes $$$[2, 3, 4]$$$.

You want to turn the current sequence of warriors powers $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$. Calculate the minimum amount of mana you need to spend on it.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of sequence $$$a$$$ and the length of sequence $$$b$$$ respectively.

The second line contains three integers $$$x, k, y$$$ ($$$1 \le x, y, \le 10^9; 1 \le k \le n$$$) — the cost of fireball, the range of fireball and the cost of berserk respectively.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that all integers $$$a_i$$$ are pairwise distinct.

The fourth line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le n$$$). It is guaranteed that all integers $$$b_i$$$ are pairwise distinct.

Output format:
Print the minimum amount of mana for turning the sequnce $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$, or $$$-1$$$ if it is impossible.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 2
5 2 3
3 1 4 5 2
3 5

Example output:
8

Example input:
4 4
5 1 4
4 3 1 2
2 4 3 1

Example output:
-1

Editorial:
The first thing we need to do is to find the occurrences of $$$b_i$$$ in the sequence $$$[a_1, a_2, \dots, a_n]$$$ — these are the monsters that have to remain. Since both spells (Fireball and Berserk) affect consecutive monsters, we should treat each subsegment of monsters we have to delete separately.
Consider a segment with $$$x$$$ monsters we have to delete such that the last monster before it has power $$$l$$$, the first monster after the segment has power $$$r$$$, and the strongest monster on the segment has power $$$p$$$.
If $$$x \bmod k \ne 0$$$, then we have to use Berserk at least $$$x \bmod k$$$ times. Let's make the strongest monster on segment kill some other monster. If $$$x < k$$$, then the strongest monster should also be killed by one of the monsters bounding the segment, so if $$$l < p$$$ and $$$r < p$$$, there is no solution.
Okay, now the number of monsters is divisible by $$$k$$$. If it is more profitable to use Fireball, we use the required number of Fireballs to kill all of them. Otherwise, we have to kill the maximum possible number of monsters with Berserk and finish the remaining ones with Fireball. If $$$l > p$$$ or $$$r > p$$$, then one of the monsters just outside the segment can kill all the monsters inside the segment; otherwise, the strongest monster should kill adjacent monsters until exactly $$$k$$$ remain, and those $$$k$$$ monsters are finished with a single Fireball.
Now we know what we need to consider when processing a single segment; all that's left is to sum the minimum required mana over all such segments. Since the total length of these segments is at most $$$n - 1$$$ and we can process each segment in linear time, we have a solution with complexity $$$O(n)$$$.