题目描述

Farmer John 沿着一条高速公路拥有一个很长的农场，可以被看作类似于一维数轴。沿着农场有 \(K\) 块草地（\(1 \leq K \leq 2\cdot 10^5\)）；第 \(i\) 块草地位于位置 \(p_i\) 并具有美味值 \(t_i\)（\(0\le t_i\le 10^9\)）。Farmer John 的死对头 Farmer Nhoj 已经将他的 \(M\) 头奶牛（\(1 \leq M \leq 2\cdot 10^5\)）放在了位置 \(f_1 \ldots f_M\) 。所有这些 \(K+M\) 个位置均是 \([0,10^9]\) 范围内的不同整数。

Farmer John 需要选择 \(N\)（\(1\le N\le 2\cdot 10^5\)）个位置（不一定是整数）放置他的奶牛。这些位置必须与 Farmer Nhoj 的奶牛已经占用的位置不同，但是 Farmer John 可以将他的奶牛放在与草地相同的位置。

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

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

格式

输入格式

输入的第一行包含 \(K\)、\(M\) 和 \(N\)。

以下 \(K\) 行每行包含两个空格分隔的整数 \(p_i\) 和 \(t_i\)。

以下 \(M\) 行每行包含一个整数 \(f_i\)。

输出格式

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

样例 #1

样例输入 #1

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

样例输出1

36

样例解释

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