Shooting Game

题目描述

You are given the coordinates of $M$ defense machines and $E$ monsters on a 1D coordinate axis.

To eliminate all monsters, you can control each machine to shoot a laser to the left, shoot a laser to the right, or remain turned off. You can also build new machines at any integer coordinate for a fixed cost of $C$ per machine (they can also be controlled to shoot in either direction).

A laser has a maximum range of $L$. It pierces through and eliminates all monsters in its path, including both endpoints. You can control the length of the laser, but it cannot exceed $L$, nor can it pass through another machine, whether it is turned on or off.

The energy cost of firing a laser is equal to the laser's length. (Note: If a monster is located exactly at a machine's coordinate, you can eliminate it by shooting a lazer in either direction at any length, including length $0$ with $0$ cost).

Find the minimum total cost required to eliminate all monsters.

输入格式

The first line contains four integers $M$, $E$, $C$, and $L$ — the number of pre-existing machines, the number of monsters, the fixed cost to build a new machine, and the maximum range of a laser.

The second line contains $M$ integers $m_1, m_2, \dots, m_M$ — the coordinates of the pre-existing machines. The third line contains $E$ integers $e_1, e_2, \dots, e_E$ — the coordinates of the monsters.

Constraints:

$1 \le M, E \le 10^6$

$1 \le C, L \le 10^9$

$1 \le m_1 \lt m_2 \lt \dots \lt m_M \le 10^9$

$1 \le e_1 \lt e_2 \lt \dots \lt e_E \le 10^9$

All input values are positive integers.

输出格式

Output a single integer — the minimum total cost to eliminate all monsters.

样例输入 #1

2 6 4 5
7 21
1 2 10 14 18 23

样例输出 #1

18

样例输入 #2

2 3 1 10
1 9
3 5 7

样例输出 #2

3