#P18837. [Croatian CPC2020] Carska Civilizacija
[Croatian CPC2020] Carska Civilizacija
[Croatian CPC2020] Carska Civilizacija
题目描述
一条街道上有 个可以建设电车站的位置,按从左到右的顺序编号为 至 。第 个位置的坐标为 ,在这里建设车站会产生数值为 的不满意度。 可以为负数。
你需要选择其中一些位置建设车站,且必须选择第 个和第 个位置。
有 名居民,第 名居民对应一个整数 。对于两个相邻的已选车站,设它们之间的距离为 ,这名居民对这一段的满意度为 。每名居民的总满意度是所有相邻已选车站之间各段满意度之和。
整个方案的总满意度等于所有居民的总满意度之和,再减去所有已选车站的不满意度之和。
请计算能够获得的最大总满意度。
输入格式
第一行包含两个整数 (,)。
第二行包含 个整数 ()。
接下来 行,第 行包含两个整数 (,)。保证 。
输出格式
输出一个整数,表示最大总满意度。
样例 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 说明
选择位置 ,相邻车站的距离依次为 。五名居民的总满意度分别为 ,总和为 ;所选车站的不满意度之和为 ,因此方案总满意度为 。