Maximizing Pasture Tastiness

Farmer John owns a long one‐dimensional farm with (K) pastures. The (i)th pasture is located at position (p_i) and has a tastiness value (t_i). Along the highway, Farmer Nhoj has already placed his (M) cows at positions (f_1, f_2, \dots, f_M). All the (K+M) positions are distinct integers in ([0,10^9]).

Farmer John is about to place (N) cows at positions of his choosing (these positions may be non‐integral) provided they do not coincide with any of Farmer Nhoj’s cows – however, they may be placed at the same positions as the pastures. Once both farmers have placed their cows, each pasture is awarded to the farmer whose cow is closest to it. In the event of a tie (i.e. when the distance from a pasture to the closest cow of each farmer is equal), the pasture goes to Farmer Nhoj.

Thus, a pasture at position (p) is captured by Farmer John if and only if [ \min_{x\in S} |p-x| < \min_{f\in F} |p-f|, ] where (S) is the set of positions chosen by Farmer John and (F = {f_1, f_2, \dots, f_M}) is the set of Farmer Nhoj’s cow positions.

Determine the maximum total tastiness that Farmer John can obtain if his cows are placed optimally.

Note: All formulas are expressed in (\LaTeX) format.

inputFormat

The first line contains three integers \(K\), \(M\) and \(N\) \( (1 \le K, M, N \le 2 \cdot 10^5)\), the number of pastures, the number of Farmer Nhoj’s cows, and the number of cows Farmer John can place respectively.

The next \(K\) lines each contain two integers \(p_i\) and \(t_i\) \( (0 \le p_i \le 10^9,\ 0 \le t_i \le 10^9)\) representing the position and tastiness value of the \(i\)th pasture.

The next \(M\) lines each contain one integer \(f_i\) \( (0 \le f_i \le 10^9)\) representing the position of one of Farmer Nhoj’s cows.

It is guaranteed that all \(K+M\) positions are distinct.

outputFormat

Output a single integer, the maximum total tastiness that Farmer John can obtain by optimally placing his \(N\) cows.

sample

3 2 1
5 10
8 5
12 7
6
10

10