| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Для Хэллоуина $m$ жителей решили расставить множество тыкв вдоль забора своего дома. Предварительно были выбраны $n$ мест, в которых можно расположить тыквы, при чем $i$-е место характеризуется двумя параметрами: $x_i$ --- расстоянием от начала забора до этого места, и $c_i$ --- уровнем недовольства жителей, если в данном месте будет расположена тыква (у каждого свое понимание об идеальной расстановке).
При этом независимо ни от чего, уже было решено, что в 1ドル$-м и $n$-м местах тыквы точно будут расположены, потому что иначе все композиция будет негармоничной.
Чтобы вычислить удовлетворенность каждого жителя расстановкой, всех попросили назвать их любимое число. Житель номер $i$ назвал число $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$.
Выведите одно число --- максимальную суммарную удовлетворенность жителей дома.
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