#USACOC2213A. Closest Cow Wins

Closest Cow Wins

Description

Farmer John owns a long farm along the highway that can be considered somewhatlike a one-dimensional number line. Along the farm, there are KK grassy patches; the ii-th patch is located at positionpip_i and has an associated tastiness value tit_i. Farmer John's nemesis, Farmer Nhoj, has already situated his MM cows at locations f1fMf_1 \ldots f_M. All K+MK+M of theselocations are distinct integers in the range [0,109][0,10^9].

Farmer John needs to pick NN locations (notnecessarily integers) for his cows to be located. These must be distinct fromthose already occupied by the cows of Farmer Nhoj, but it is possible for Farmer John to place his cows at the same locations as grassy patches.

Whichever farmer owns a cow closest to a grassy patch can claim ownership ofthat patch. If there are two cows from rival farmers equally close to thepatch, then Farmer Nhoj claims the patch.

Given the locations of Farmer Nhoj's cows and the locations and tastiness valuesof the grassy patches, determine the maximum total tastiness Farmer John's cowscan claim if optimally positioned.

  • 1K21051 \leq K \leq 2\cdot 10^5
  • 0ti1090\le t_i\le 10^9
  • 1M21051 \leq M \leq 2\cdot 10^5
  • 1N21051\le N\le 2\cdot 10^5

Input Format

The first line contains KK, MM, and NN.

The next KK lines each contain two space-separated integers pip_i and tit_i.

The next MM lines each contain a single integer fif_i.

Output Format

An integer denoting the maximum total tastiness. Note that the answer to thisproblem can be too large to fit into a 32-bit integer, so you probably want touse 64-bit integers (e.g., long longs in C or C++).

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

If Farmer John places cows at positions 11.511.5 and 88 then he can claim a total tastiness of 10+12+14=3610+12+14=36.

Problem Credit

Problem credits: Brian Dean