제국 문명

시간 제한1.5초메모리 제한512 MB

요약

첫 번째와 마지막 위치를 반드시 포함하는 정류장 부분집합을 고릅니다. 인접한 두 정류장 사이 거리 d마다 모든 거주자의 |d - d_i| 합을 더하고, 정류장의 불만도 c를 뺀 값을 최대화합니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 분할 정복, 기하
정답자: 아직 제출이 없습니다

문제

대재앙 이후 말나르 씨가 새로운 문명을 세우려 한다. 그가 가장 먼저 하려는 일은 제국의 중심 도로에 트램 노선을 다시 세우는 것이다.

도로를 따라 $n$ 개의 후보 위치가 있고, 말나르 씨는 그중 일부를 트램 정류장으로 고른다. 첫 번째 위치와 $n$ 번째 위치에는 회차장이 있어서 반드시 선택해야 한다.

각 위치 $i$ 에는 도로 시작점에서의 거리 $x_i$ 와, 그곳에 정류장을 세웠을 때 주민들이 느끼는 불만 $c_i$ 가 정해져 있다. 어떤 곳에는 표를 늘 비싸게 파는 매점이 있고, 어떤 곳에는 맛있는 빵집이 있다.

이 노선을 이용할 주민은 $m$ 명이다. 주민 $i$ 는 길이 $d_i$ 만큼 타는 것을 싫어하며, 선택된 정류장들을 다음과 같이 평가한다.

이 주민의 전체 만족도는 선택된 정류장 중 연속한 두 정류장의 쌍마다 만족도를 더한 값이다.
거리가 $d$ 인 연속한 두 정류장의 만족도는 $|d - d_i|$ 이다.

말나르 씨는 $m$ 명 모두의 만족도를 더한 뒤, 선택된 모든 정류장 $k$ 의 불만 $c_k$ 를 뺀다. 정류장을 최적으로 골랐을 때 얻을 수 있는 최대 값을 구하라.

입력

첫 줄에 자연수 $n$ ( $2 \le n \le 100\,000$ )과 $m$ ( $1 \le m \le 100\,000$ )이 주어진다.

둘째 줄에는 $m$ 개의 정수 $d_i$ ( $0 \le d_i \le 10^7$ )가 주어진다.

이어서 $n$ 개의 줄에 후보 위치가 하나씩 주어진다. 각 줄에는 위치 $x_i$ ( $0 \le x_i \le 10^7$ )와 불만 $c_i$ ( $0 \le |c_i| \le 10^{12}$ )가 정수로 주어지며, $x_1 < x_2 < \ldots < x_n$ 이다.

출력

가능한 최대 만족도를 한 줄에 출력한다.

힌트

세 번째 예제 설명: 최적의 선택은 위치 1, 3, 5, 7, 9이다. 연속한 거리는 차례로 6, 17, 49, 25이고, 주민들의 만족도는 차례로 61, 159, 89, 275, 171이다. 만족도의 합은 755이고, 선택한 정류장의 불만 합은 618이므로 최종 결과는 137이다.

예제3

예제 1
입력
```
2 1
10
0 5
20 3
```
예상 출력
```
2
```
예제 2
입력
```
3 3
3 7 10
2 20
5 4
10 -3
```
예상 출력
```
-1
```

예제 3

입력

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

예상 출력