문제
농부 John은 일직선으로 이루어진 고속도로를 따라 긴 농장을 소유하고 있습니다.
농장을 따라 K개의 잔디밭이 있고(1≤K≤2⋅105), i번째 잔디밭은 위치 pi에 있고 맛있는 값인 ti(0≤ti≤109)를 가지고 있습니다. Farmer John의 숙적인 Farmer Nhoj는 위치 f1...fM에 M마리의 소(1≤M≤2⋅105)를 배치했습니다. 이러한 모든 K+M 위치는 [0,109] 범위의 고유한 정수입니다.
농부 John은 소를 배치하기 위해 위치 N(1≤N≤2⋅105, 반드시 정수일 필요는 없음)을 선택해야 합니다. 이 위치는 Farmer Nhoj의 소가 이미 점유한 위치와 달라야 하지만 Farmer John은 그의 소를 잔디와 같은 위치에 놓을 수 있습니다.
초원에 가장 가까운 소를 소유한 농부가 초원을 소유합니다. 두 농부의 소 두 마리가 초원에서 등거리에 있다면 Farmer Nhoj가 초원을 소유하고 있습니다.
Farmer Nhoj의 젖소 위치와 풀의 위치 및 맛있는 값이 주어지면 Farmer John의 젖소가 최적으로 배치되었을 때 얻을 수 있는 최대 총 맛 값을 찾으십시오.
입력
입력의 첫 번째 줄에는 K, M 및 N이 포함됩니다. 다음 K 라인은 각각 공백으로 구분된 두 정수 pi와 ti를 포함합니다.
다음 M 라인은 각각 정수 fi를 포함합니다.
출력
최대 총 맛있는 값을 나타내는 정수를 출력합니다. 이 질문에 대한 답변은 32비트 정수 유형으로 저장되지 않을 수 있으며 64비트 정수 유형(예: C 또는 C++의 "long long")을 사용해야 할 수도 있습니다.
예제1
6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11
36