2024.8.18

    
//2024.8.18
//by white_ice
#include
//#include"need.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 2000006;
int n,m,w,k;
int h[oo],l[oo],r[oo];
int ned[oo];int f[1003][1003];
int st[oo],sum[oo];
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> w;
    for(int i=1;i<=n;i++)cin >> k,h[i] = w - k;
    for(itn x,y,i=1;i<=m;i++){
        cin >> x >> y;
        l[i] = r[i] = x;
        while (l[i]>1&&y>h[l[i]]) l[i]--;
        while (r[i]<n&&y>h[r[i]]) r[i]++;
        ned[2*i-1] = l[i];ned[2*i] = r[i];
    }
    sort(ned+1,ned+2*m+1);
    int cnt = unique(ned+1,ned+2*m+1)-ned-1;
    for (itn i=1;i<=m;i++)
        l[i] = lower_bound(ned+1,ned+cnt+1,l[i])-ned,
        r[i] = lower_bound(ned+1,ned+cnt+1,r[i])-ned;
    for (int len=1;len<=cnt;len++){
        for (itn i=1;i+len-1<=cnt;i++){
            int j=i+len-1;
            for (itn k=1;k<=m;k++) if(i<=l[k]&&r[k]<=j){sum[l[k]]++;sum[r[k]+1]--;}
            for (itn k=i;k<=j;k++){
                sum[k] += sum[k-1];
                int p = f[i][k-1]+f[k+1][j];
                f[i][j] = max(f[i][j],sum[k]*(sum[k]-1)/2+p);
            }
            for (itn k=i;k<=j+1;k++)sum[k] = 0;
        }
    }
    cout << f[1][cnt] << flush;
    exit(0);
}
	

    
//2024.8.18
//by white_ice
//#120. 【2020.11.25 NOIP模拟赛 T3】异或
#include
//#include"need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int mod = 998244353;
constexpr int oo = 3e5 + 10;
int n, x;int ned[oo];
int st[oo];int pow2[oo];
int out;
int tot = 1;
int sum[oo*60],ch[oo*60][2];
__inline void insert(int x,int v){
    int u = 1;
    sum[u] += v;
    for (int i=59;~i;i--) {
        if (x>>i&1){if (!ch[u][1])ch[u][1] = ++tot;u = ch[u][1];}
        else {if (!ch[u][0])ch[u][0] = ++tot;u = ch[u][0];}
        sum[u] += v;
    }
}
__inline int query(int v){
    int u = 1;int res = 0;
    for (int i=59;~i;i--) {
        if (x>>i&1)
            u=ch[u][(v>>i&1)^1];
        else {
            res += sum[ch[u][(v>>i&1)^1]];
            res %= mod;
            u = ch[u][v>>i&1];
        }
        if (!u) return res;
    }
    res += sum[u];
    return res;
}
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> x;
    for (int i=1;i<=n;i++)cin >> st[i];
    sort(st+1,st+n+1);
    for (int i=1;i<=n;i++){
        ned[i] = query(st[i])+1;
        insert(st[i],ned[i]);
        out = (out+ned[i])%mod;
    }
    cout << out << flush;
    exit(0);
}
</code>