Penguinland is an infinite number line with n monsters. The -th monster is initially at position on the number line, with health . It is guaranteed that no two monsters share the same initial position.
Today, Brian the penguin wishes to defeat all the monsters! To defeat them, Brian has planted mines at certain positions. The -th mine is located at position . Detonating a mine instantly destroys all monsters standing on that position, and each mine can be detonated any number of times. However, each detonation costs dollar. It is guaranteed that no two mines are planted at the same position.
In addition to detonating mines, Brian can also perform two types of operations:
Move a monster left or right by unit along the number line.
Increase or decrease a monster’s health by .
Each operation costs dollar to execute.
A monster is considered defeated if its health reaches or if it is destroyed by a mine. Help Brian find the minimum cost (in dollars) needed to defeat all the monsters.
输入格式
Your program must read from standard input.
The first line of input contains two space-separated integers and .
The following lines each contain two space-separated integers. The -th of these lines contains and .
The last line of input contains space-separated integers .
输出格式
Your program must print to standard output.
Output a single integer, the minimum cost (in dollars) needed to defeat all the monsters.
The output should contain only a single integer. Do not print any additional text such as Enter a number or The answer is.
