3630. 最近的母牛获胜

【题目描述】

$Farmer$ $John$ 沿着一条高速公路拥有一个很长的农场，可以被看作类似于一维数轴。沿着农场有 $K$ 块草地（$1≤K≤2*10^5$）；第 $i$ 块草地位于位置 $p_i$ 并具有美味值 $t_i$（$0≤t_i≤10^9$）。$Farmer$ $John$ 的死对头 $Farmer$ $Nhoj$ 已经将他的 $M$ 头奶牛（$1≤M≤2*10^5$）放在了位置 $f_1…f_M$ 。所有这些 $K+M$ 个位置均是 $[0,10^9]$ 范围内的不同整数。$Farmer$ $John$ 需要选择 $N（1≤N≤2*10^5）$个位置（不一定是整数）放置他的奶牛。这些位置必须与 $Farmer$ $Nhoj$ 的奶牛已经占用的位置不同，但是 $Farmer$ $John$ 可以将他的奶牛放在与草地相同的位置。

拥有最靠近某个草地的奶牛的农夫拥有这一草地。如果来自两方农夫的两头奶牛距这一草地相等，则 $Farmer$ $Nhoj$ 拥有该草地。

给定 $Farmer$ $Nhoj$ 的奶牛的位置以及草地的位置和美味值，求 $Farmer$ $John$ 的奶牛以最优方式放置时可以达到的最大总美味值。

【输入格式】

输入的第一行包含 $K、M$ 和 $N$。以下 $K$ 行每行包含两个空格分隔的整数 $p_i$ 和 $t_i$。

接下来 $M$ 行每行包含一个整数 $f_i$。

【输出格式】

输出一个整数，表示最大总美味值。注意这个问题的答案可能无法用 $32$ 位整数型存储，你可能需要使用 $64$ 位整数型（例如，$C$ 或 $C++$ 中的 "$long$ $long$"）。

【样例输入】

6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11

【样例输出】

36

【样例说明】

如果 $Farmer$ $John$ 将奶牛放在位置 $11.5$ 和 $8$ 则他可以得到总美味值 $10+12+14=36$。

【数据规模与约定】

$1≤K,M,N≤2\times 10^5,0≤f_i≤10^9,0≤t_i≤10^9$。

【来源】

$USACO$ $2021.12$ 银组第一题