Расстановка тыкв
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Поскольку жители дома хотят, чтобы отмечание праздника всех порадовало, было решено максимизировать суммарную удовлетворенность расстановкой тыкв. Однако также было учтено суммарное недовольство жителей всеми выбранными местами. Таким образом, если тыквы расположить в местах $$$j_1$$$, $$$j_2$$$, ..., $$$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$$$.

Выходные данные

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

Примеры

Входные данные
2 1
10
0 5
20 3
Выходные данные
2
Входные данные
3 3
3 7 10
2 20
5 4
10 -3
Выходные данные
-1
Входные данные
9 5
30 64 2 93 67
0 81
1 256
6 251
13 256
23 180
52 256
72 94
77 256
97 12
Выходные данные
137