P7990 [USACO21DEC] Closest Cow Wins S

Farmer John owns a very long farm along a highway, which can be viewed as a one-dimensional number line. Along the farm there are $K$ patches of grass ($1 \leq K \leq 2\cdot 10^5$); the $i$-th patch is at position $p_i$ and has tastiness $t_i$ ($0\le t_i\le 10^9$). Farmer John’s rival, Farmer Nhoj, has already placed his $M$ cows ($1 \leq M \leq 2\cdot 10^5$) at positions $f_1 \ldots f_M$. All of these $K+M$ positions are distinct integers in the range $[0,10^9]$. Farmer John needs to choose $N$ positions ($1\le N\le 2\cdot 10^5$) (not necessarily integers) to place his cows. These positions must be different from the positions already occupied by Farmer Nhoj’s cows, but Farmer John may place his cows at the same positions as grass patches. The farmer who has the cow closest to a grass patch owns that patch. If one cow from each farmer is at the same distance from a patch, then Farmer Nhoj owns that patch. Given the positions of Farmer Nhoj’s cows and the positions and tastiness values of the grass patches, find the maximum total tastiness Farmer John can obtain if he places his cows optimally.

The first line contains $K$, $M$, and $N$. The next $K$ lines each contain two space-separated integers $p_i$ and $t_i$. The next $M$ lines each contain one integer $f_i$.

Output one integer, the maximum total tastiness value. Note that the answer may not fit in a 32-bit integer type, so you may need to use a 64-bit integer type (for example, "long long" in C or C++).

[Sample Explanation] If Farmer John places cows at positions $11.5$ and $8$, then he can obtain total tastiness $10+12+14=36$. Translated by ChatGPT 5