The Ultra Gigantic Duck

After a lengthy quarrel (which half ruined your friendship), you finally persuade your friend to lend you their technological marvel, the Ultra Gigantic Duck for $N$ days. Whilst scrutinizing the manual, you learn that the Ultra Gigantic duck must be stored AND used indoors at all times. To your surprise, you also uncover that the Ultra Gigantic Duck's width changes every day!

Specifically, on day $i$, the Ultra Gigantic Duck morphs into a width of $K_i$. This leads you to the realisation that your garage is incapable of storing it (probably also because your gamer setup takes up half your garage).‎ Without a place to store it, your hopes and dreams of using this masterpiece would be crushed.

Unfortunately for you, you cannot possibly risk storing the Ultra Gigantic Duck outside, nor return it to your friend, unless you want to permanently ruin your friendship. Without another option, you seek the warehouses in town.

There are $M$ warehouses in town. Each warehouse $j$ has a daily storage fee of $C_j$ and a width of $W_j$, and can only store the Ultra Gigantic Duck on day $i$ if $W_j$ is strictly larger than $K_i$.

You want to know the minimum amount of money you need to spend on storage fees before you return the Ultra Gigantic Duck back to your friend. If it is impossible to store the Ultra Gigantic Duck for any one of the $N$ days, output $-1$.

NOTE

• Make sure to use a 64-bit integer type to avoid integer overflow.
• Moving the Ultra Gigantic Duck between warehouses is allowed
• There are no moving fees (the warehouses subsidise it)

Constraints

• $1 \le N,M \le 10^5$
• $1 \le K_i \le 10^9$ for all $1 \le i \le N$
• $1 \le W_j \le 10^9$ for all $1 \le j \le M$
• $1 \le C_j \le 10^5$ for all $1 \le j \le M$

Subtasks

• Subtask 1 (10%): $K_i = K_{i+1}$ for all $1 \le i \le N-1$
• Subtask 2 (20%): $K_i < W_j$ for all $1 \le i \le N$ and all $1 \le j \le M$
• Subtask 3 (20%): $N \le 1000$, $M \le 1000$
• Subtask 4 (50%): No further constraints

Input

• The first line contains two space-separated integers, $N$ and $M$ — the number of days before your friend takes the Ultra Gigantic Duck back and the number of warehouses you find in town.
• The second line contains $N$ space-separated integers, $K_1,K_2,...,K_N$ — the widths of the Ultra Gigantic Duck every day.
• The third line contains $M$ space-separated integers, $W_1,W_2,...,W_M$ — the widths of each warehouse.
• The fourth line contains $M$ space-separated integers, $C_1,C_2,...,C_M$ — the daily storage fees of each warehouse.

Output

You should output a single integer — the minimum amount of money you need to spend on storage fees before you return the Ultra Gigantic Duck back to your friend. If it is impossible to store the Ultra Gigantic Duck for any one of the $N$ days, output $-1$

Sample explanation

In sample 1, you can choose any warehouse as all of their widths are larger than all of the widths of the Ultra Gigantic Duck. The optimal solution would be to use the cheapest warehouse throughout the N days. This would be warehouse 2, at 10 dollars per day. This results in a total of 10 * 3 = 30 dollars.

In sample 2, the optimal solution would be to choose warehouse 2 on day 1, warehouse 2 on day 2, warehouse 4 on day 3, and warehouse 4 on day 4. This results in a total of 1 + 1 + 3 + 3 = 8 dollars.

In sample 3, neither of the warehouses can store the Ultra Gigantic Duck on any day.