Umbrella Coverage

Farmer John's cows are getting wet on a rainy day! There are \(N\) cows located along a number line with positions ranging from 1 to \(M\). The \(i\)-th cow is located at coordinate \(X_i\), and no two cows share the same stall.

An umbrella placed to cover the segment from coordinate \(a\) to \(b\) (with \(a \le b\)) has a width defined by \(\text{width} = b - a + 1\). For each possible width \(W\) (from 1 to \(M\)), its cost is given by \(C_W\). Note that a larger umbrella does not necessarily cost more than a smaller one.

Your task is to help Farmer John choose a set of umbrellas such that every cow is covered and the total cost is minimized. Umbrellas are allowed to overlap.

inputFormat

The first line contains two integers, \(N\) and \(M\) (\(1 \le N \le 5000\), \(1 \le M \le 100000\)).

The second line contains \(N\) space-separated integers \(X_1, X_2, \dots, X_N\) (each \(1 \le X_i \le M\)), representing the positions of the cows. It is guaranteed that all \(X_i\) are distinct.

The third line contains \(M\) space-separated integers. The \(i\)-th integer represents the cost \(C_i\) of an umbrella of width \(i\) (\(1 \le C_i \le 1000000\)).

outputFormat

Output a single integer denoting the minimum total cost required to cover all cows.

sample

3 10
2 5 8
5 6 7 8 9 10 11 12 13 14

11