记录编号	571952	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	最近的母牛获胜	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	1.109 s
提交时间	2022-06-26 15:48:05	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
////////////////////////
const int N=2e5+50;
int kc,mc,nc;
struct K
{
    ull t;
    int p;
}k[N];//草地 
int f[N];//母牛
ull a[N<<1],aj; 
ull ans;
bool cmp(K x,K y){return x.p<y.p;}
inline void solve1()
{
    int k1=1,k2=1,k3,k4;
    int f1=0,f2=1;
    ull sum1,sum2,sum3;
    while(f2<mc&&k1<=kc)
    {
        while(f[f2]<k[k2].p) f1=f2++;
        while(k[k2].p<f[f2]&&k2<=kc) k2++;
        k2--;
//        cout<<"T1:"<<k1<<" "<<k2<<"|"<<f1<<" "<<f2<<endl;
        //
        sum1=sum2=sum3=0;
        rep(i,k1,k2) sum3+=k[i].t;
        //
        k3=k4=k1;
        sum1=sum2=k[k1].t;
        while(k3<k2)
        {
            if(k[k4+1].p-k[k3].p<f[f2]+k[k3].p-k[k4+1].p-f[f1]&&k4<k2) 
            {
                sum1+=k[++k4].t;
                sum2=max(sum2,sum1);   
            }
            else sum1-=k[k3++].t;
//            if(k1==2&&k2==3)
//            {
//                cout<<k3<<" "<<k4<<":"<<sum1<<endl;
//            }
        }
        //
        a[++aj]=sum2;
//        if(a[aj]>40) cout<<k1<<"&"<<k2<<endl;
        a[++aj]=sum3-sum2;
//        if(a[aj]>40) cout<<k1<<"&2&"<<k2<<":"<<sum2<<" "<<sum3<<endl;
        k1=++k2;
    }
}
int main()
{
    freopen("Closest_Cow_Wins.in","r",stdin);
	freopen("Closest_Cow_Wins.out","w",stdout);
    kc=read(),mc=read(),nc=read();
    rep(i,1,kc) k[i].p=read(),k[i].t=read();
    rep(i,1,mc) f[i]=read();
    sort(k+1,k+kc+1,cmp);
    f[++mc]=2e9+N;
    f[++mc]=-(1e9+N);
    sort(f+1,f+mc+1);
    solve1();
    sort(a+1,a+1+aj);
    drep(i,aj,aj-nc+1) ans+=a[i];
//    cout<<"a:\n";
//    drep(i,aj,1) cout<<a[i]<<" ";
//    cout<<endl;
    cout<<ans<<endl;
    return 0;
}
//6 5 3
//18 9
//20 11
//11 11
//5 13
//14 2
//9 8
//12
//4
//16
//0
//6