#include<bits/stdc++.h>
using namespace std;
int n,m,w;
int h[20005],L[205],R[205],a[205<<1],s[205<<1],f[20005][20005];
int main()
{
    scanf("%d %d %d",&n,&m,&w);
    for(int i=1; i<=n; i++)
        scanf("%d",&h[i]);
    int tot=0;
    for(int i=1; i<=m; i++)
    {
        int p,j;
        scanf("%d%d",&p,&j);
        for(L[i]=p; L[i]>1&&j>w-h[L[i]]; --L[i]);
        for(R[i]=p; R[i]<n&&j>w-h[R[i]]; ++R[i]);
        a[++tot]=L[i];
        a[++tot]=R[i];
    }
    sort(a+1,a+2*m+1);
    n=unique(a+1,a+2*m+1)-(a+1);
    for(int i=1; i<=m; i++)
    {
        L[i]=lower_bound(a+1,a+n+1,L[i])-a;
        R[i]=lower_bound(a+1,a+n+1,R[i])-a;
    }
    for(int d=0; d<n; d++)
        for(int i=1; i+d<=n; i++)
        {
            int j=i+d;
            for(int k=i-1; k<=j+1; k++)
                s[k]=0;
            for(int k=1; k<=m; k++)
                if(i<=L[k]&&R[k]<=j)
                    ++s[L[k]],--s[R[k]+1];
            for(int k=i+1; k<=j; k++)
                s[k]+=s[k-1];
            for(int k=i; k<=j; k++)
                f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+(s[k]*(s[k]-1)>>1));
        }
    printf("%d\n",f[1][n]);
    return 0;
}

造数据代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,w;
int h[20005],L[205],R[205],a[205<<1],s[205<<1],f[20005][20005];
signed main()
{
    char C[100005];
    srand(time(0));
    for(int monster=1; monster<=18; monster++)
    {
        sprintf(C,"question%d.in",monster);
        freopen(C,"w",stdout);
        n=rand()%20000;
        if(n==0) n=20000;
        else if(n<2) n=2;
        m=rand()%200;
        if(m==0) m=200;
        w=rand()%2000000;
        if(w==0) w=2000000;
        cout<<n<<" "<<m<<" "<<w<<endl;
//      int x=rand()%1000000;
        for(int i=1; i<=n; i++)
          h[i]=rand()%1000000,cout<<h[i]<<" ";
          int tot=0;
          cout<<endl;
         for(int i=1; i<=m; i++)
    {
        int p,j;
        p=rand()%n;
        if(p==0) p=n;
        j=rand()%1000000;
        if(j==0) j=1000000;
        cout<<p<<" "<<j<<endl;
        for(L[i]=p; L[i]>1&&j>w-h[L[i]]; --L[i]);
        for(R[i]=p; R[i]<n&&j>w-h[R[i]]; ++R[i]);
        a[++tot]=L[i];
        a[++tot]=R[i];
    } 
        fclose(stdin);
        sprintf(C,"question%d.out",monster);
        freopen(C,"w",stdout);
        sort(a+1,a+2*m+1);
    n=unique(a+1,a+2*m+1)-(a+1);
    for(int i=1; i<=m; i++)
    {
        L[i]=lower_bound(a+1,a+n+1,L[i])-a;
        R[i]=lower_bound(a+1,a+n+1,R[i])-a;
    }
    for(int d=0; d<n; d++)
        for(int i=1; i+d<=n; i++)
        {
            int j=i+d;
            for(int k=i-1; k<=j+1; k++)
                s[k]=0;
            for(int k=1; k<=m; k++)
                if(i<=L[k]&&R[k]<=j)
                    ++s[L[k]],--s[R[k]+1];
            for(int k=i+1; k<=j; k++)
                s[k]+=s[k-1];
            for(int k=i; k<=j; k++)
                f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+(s[k]*(s[k]-1)>>1));
        }
    printf("%d\n",f[1][n]);
        fclose(stdin);
    }
    return 0;
}