#P18837. [Croatian CPC2020] Carska Civilizacija

[Croatian CPC2020] Carska Civilizacija

[Croatian CPC2020] Carska Civilizacija

题目描述

一条街道上有 nn 个可以建设电车站的位置,按从左到右的顺序编号为 11 至 nn。第 ii 个位置的坐标为 xix_i,在这里建设车站会产生数值为 cic_i 的不满意度。cic_i 可以为负数。

你需要选择其中一些位置建设车站,且必须选择第 11 个和第 nn 个位置。

有 mm 名居民,第 jj 名居民对应一个整数 djd_j。对于两个相邻的已选车站,设它们之间的距离为 dd,这名居民对这一段的满意度为 ∣d−dj∣|d-d_j|。每名居民的总满意度是所有相邻已选车站之间各段满意度之和。

整个方案的总满意度等于所有居民的总满意度之和,再减去所有已选车站的不满意度之和。

请计算能够获得的最大总满意度。

输入格式

第一行包含两个整数 n,mn,m(2≤n≤1052\le n\le10^5,1≤m≤1051\le m\le10^5)。

第二行包含 mm 个整数 d1,…,dmd_1,\ldots,d_m(0≤dj≤1070\le d_j\le10^7)。

接下来 nn 行,第 ii 行包含两个整数 xi,cix_i,c_i(0≤xi≤1070\le x_i\le10^7,−1012≤ci≤1012-10^{12}\le c_i\le10^{12})。保证 x1<x2<⋯<xnx_1<x_2<\cdots<x_n。

输出格式

输出一个整数,表示最大总满意度。

样例 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

输出

137

样例 3 说明

选择位置 1,3,5,7,91,3,5,7,9,相邻车站的距离依次为 6,17,49,256,17,49,25。五名居民的总满意度分别为 61,159,89,275,17161,159,89,275,171,总和为 755755;所选车站的不满意度之和为 618618,因此方案总满意度为 137137。