호박 배치

시간 제한2초메모리 제한1024 MB

요약

첫 번째와 마지막 위치를 반드시 포함해 울타리 위치를 고르고, 인접한 간격에서 얻는 만족도 합에서 선택한 위치의 불만도 합을 뺀 값을 최대화합니다.

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

문제

할로윈을 맞아 $m$ 명의 주민이 집 울타리를 따라 호박을 여러 개 놓기로 했다. 호박을 놓을 수 있는 후보 위치가 $n$ 개 미리 정해져 있다. $i$ 번째 위치는 두 값으로 나타낸다. $x_i$ 는 울타리 시작점에서 그 위치까지의 거리이고, $c_i$ 는 그 위치에 호박을 놓았을 때 주민들이 느끼는 불만 수준이다.

다른 조건과 상관없이 1번 위치와 $n$ 번 위치에는 반드시 호박을 놓는다.

주민 $i$ 는 자신이 좋아하는 수 $d_i$ 를 말했다. 주민 $i$ 는 거리가 $d$ 만큼 떨어진 인접한 두 호박에서 $|d - d_i|$ 만큼 만족한다. 주민의 전체 만족도는 인접한 모든 호박 쌍에 대한 이 값의 합이다.

호박을 위치 $j_1, j_2, \ldots, j_k$ 에 (울타리를 따라 가까운 순서대로) 놓으면 전체 만족도는 $\left(\sum_{i=1}^{m} \sum_{t=2}^{k} |x_{j_t} - x_{j_{t-1}} - d_i|\right) - \left(\sum_{t=1}^{k} c_{j_t}\right)$ 로 계산된다.

주민들은 호박을 놓을 위치를 최적으로 골라 이 전체 만족도를 최대로 만들려고 한다.

입력

첫 줄에 후보 위치의 개수 $n$ 과 주민의 수 $m$ 이 공백으로 구분되어 주어진다 ( $2 \leq n \leq 10^5$ , $1 \leq m \leq 10^5$ ).

둘째 줄에는 각 주민이 좋아하는 수 $d_i$ 가 공백으로 구분되어 $m$ 개 주어진다 ( $0 \leq d_i \leq 10^7$ ).

이어서 $n$ 개의 줄에 각 후보 위치의 매개변수 $x_i$ 와 $c_i$ 가 주어진다 ( $0 \leq x_i \leq 10^7$ , $0 \leq |c_i| \leq 10^{12}$ ). $x_1 < x_2 < \ldots < x_n$ 이 보장된다.

출력

주민들의 전체 만족도의 최댓값을 한 개의 정수로 출력한다.

예제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

예상 출력