Penguinland Monster Defeat

Brian the penguin faces a challenge in Penguinland, an infinite number line with n monsters. The \(i\)-th monster is initially at position \(a[i]\) with health \(h[i]\), and no two monsters share the same position. Brian has planted k mines at positions \(x[j]\). Detonating a mine costs \(1\) dollar and instantly destroys all monsters standing on that position. Each mine can be detonated any number of times. In addition, Brian can move a monster one unit left or right, or adjust its health by \(1\) (both operations costing \(1\) dollar each). A monster is considered defeated if its health reaches \(0\) or if it is destroyed by a mine.

Your task is to determine the minimum cost (in dollars) needed to defeat all the monsters.

Explanation: For each monster, you have two options:

• Health Reduction: Reduce its health completely at a cost of \(h[i]\) dollars.
• Mine Strategy: Move the monster to one of the available mine positions, incurring a movement cost of \(|a[i]-x[j]|\). Then, by detonating the mine (which costs \(1\) dollar per mine used, regardless of the number of monsters assigned to that mine), the monster is instantly defeated.

If a monster is moved to the position \(x[j]\), the individual cost is \(|a[i]-x[j]|\) dollars, and if you assign one or more monsters to the same mine, you pay an extra \(1\) dollar once for that mine detonation. You should choose the best option for each monster (and possibly group monsters by their optimal mine) in order to minimize the total expense.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with two integers \(n\) and \(k\) (\(1 \le n, k \le 10^5\)), representing the number of monsters and the number of mines respectively.

The second line contains \(n\) integers \(a[1], a[2], \ldots, a[n]\) denoting the positions of the monsters. It is guaranteed that all positions are distinct.

The third line contains \(n\) integers \(h[1], h[2], \ldots, h[n]\) where \(h[i]\) is the health of the \(i\)-th monster.

The fourth line contains \(k\) integers \(x[1], x[2], \ldots, x[k]\) indicating the positions of the mines. All mine positions are distinct.

outputFormat

Output a single integer: the minimum cost (in dollars) needed to defeat all the monsters.

sample

1 1
10
5
8

3