P5383: 小牛比赛
传统题
1.000s
时间限制
256MB
内存限制
2 提交
2 解决
【题目描述】
Farmer John 沿着一条高速公路拥有一个很长的农场，可以被看作类似于一维数轴。沿着农场有K块草地（1≤K≤2·10
5）；第i块草地位于位置pi并具有美味值ti（0≤ti≤10
9）。Farmer John 的死对头 Farmer Nhoj 已经将他的M头奶牛（1≤M≤2·10
5）放在了位置f1…fM。所有这些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行每行包含两个空格分隔的整数pi和ti。
以下M行每行包含一个整数fi。
输出格式（输出至终端 / 标准输出）：
输出一个整数，表示最大总美味值。注意这个问题的答案可能无法用 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。