Расстановка тыкв

Для Хэллоуина $m$ жителей решили расставить множество тыкв вдоль забора своего дома. Предварительно были выбраны $n$ мест, в которых можно расположить тыквы, при чем $i$-е место характеризуется двумя параметрами: $x\_i$ --- расстоянием от начала забора до этого места, и $c\_i$ --- уровнем недовольства жителей, если в данном месте будет расположена тыква (у каждого свое понимание об идеальной расстановке).

При этом независимо ни от чего, уже было решено, что в $1$-м и $n$-м местах тыквы точно будут расположены, потому что иначе все композиция будет негармоничной.

Чтобы вычислить удовлетворенность каждого жителя расстановкой, всех попросили назвать их любимое число. Житель номер $i$ назвал число $d\_i$, которое означает, что

• уровень его удовлетворенности двумя соседними тыквами на расстоянии $d$ друг от друга равен $|d - d\_i|$;
• суммарная удовлетворенность жителя равна сумме удовлетворенности для каждых двух соседних тыкв.

Поскольку жители дома хотят, чтобы отмечание праздника всех порадовало, было решено максимизировать суммарную удовлетворенность расстановкой тыкв. Однако также было учтено суммарное недовольство жителей всеми выбранными местами. Таким образом, если тыквы расположить в местах $j\_1$, $j\_2$, \ldots, $j\_k$ (в порядке отдаления от начала забора), суммарная удовлетворенность будет вычисляться как $\left(\sum\limits\_{i=1}^m \sum\limits\_{t=2}^k |x\_{j\_t} - x\_{j\_{t - 1}} - d\_i|\right) - \left(\sum\limits\_{t=1}^k c\_{j\_t}\right) \text{.}$

Выведите максимальную суммарную удовлетворенность, которую можно достичь, оптимально выбрав места для тыкв.

В первой строке ввода через пробел даны два числа $n$ и $m$ --- количество мест для тыкв и количество жителей дома, соответственно ($2 \leqslant n \leqslant 10^5$; $1 \leqslant m \leqslant 10^5$).

Во второй строке через пробел перечислены $m$ чисел $d\_i$ --- любимые числа каждого жителя ($0 \leqslant d\_i \leqslant 10^7$).

В каждой из следующих $n$ строк записаны числа $x\_i$ и $c\_i$ --- параметры выделенных мест для расположения тыкв ($0 \leqslant x\_i \leqslant 10^7$; $0 \leqslant |c\_i| \leqslant 10^{12}$). Гарантируется, что $x\_1 < x\_2 < \ldots < x\_n$.

Выведите одно число --- максимальную суммарную удовлетворенность жителей дома.