410633: GYM104067 H Расстановка тыкв

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

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

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

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

• уровень его удовлетворенности двумя соседними тыквами на расстоянии $$$d$$$ друг от друга равен $$$|d - 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