RT，WA #18 RE #20，也不知道哪里错 QwQ

#include<cstdio>
#define ll long long
#define N_ 2502
#define M_ 10005
int n,m,k;
ll pts[N_],ans;
bool rch[N_][N_];
void max_s(ll &p,ll q){
    if(q>p)p=q;
}
struct eg{
    int to,last;
}edge[M_<<1];
int head[N_],toteg;
void addeg(int p,int q){
    edge[++toteg]=(eg){q,head[p]};
    head[p]=toteg;
    edge[++toteg]=(eg){p,head[q]};
    head[q]=toteg;
}
struct node{
    int pos,step;
}que[N_];
int qf,qr;
bool vis[N_];
void bfs(int s){
    qf=qr=0;
    que[qr++]=(node){s,-1};
    for(;qf<qr;qf++){
        int u=que[qf].pos;
        int stp=que[qf].step;
        if(u^s)rch[s][u]=true;
        vis[u]=true;
        for(int i=head[u],v;i;i=edge[i].last){
            v=edge[i].to;
            if(!vis[v]&&stp<k){
                que[qr++]=(node){v,stp+1};
            }
        }
    }
    while(qr--){
        vis[que[qr].pos]=false;
    }
}
int f[N_][3];
void upd(int u,int i){
    if(f[u][2]&&pts[i]<=pts[f[u][2]])return;
    int j=2;
    if(!f[u][1]||pts[i]>=pts[f[u][1]]){
        j=1; f[u][2]=f[u][1];
    }
    if(!f[u][0]||pts[i]>=pts[f[u][0]]){
        j=0; f[u][1]=f[u][0];
    }
    f[u][j]=i;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=2;i<=n;i++)scanf("%lld",&pts[i]);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        addeg(u,v);
    }
    for(int i=1;i<=n;i++){
        bfs(i);
        /*for(int j=1;j<=n;j++){
            printf("%d ",rch[i][j]);
        }
        putchar('\n');*/
    }
    for(int i=2;i<=n;i++){
        for(int j=2;j<=n;j++){
            if(j==i)continue;
            if(rch[1][j]&&rch[j][i])upd(i,j);
            //if(rch[1][i]&&rch[r])
        }
    }
    /*for(int i=2;i<=n;i++){
        printf("%d:",i);
        for(int j=0;j<3;j++){
            if(!f[i][j])break;
            printf("(%d,%lld)",f[i][j],pts[f[i][j]]);
        }
        putchar('\n');
    }*/
    for(int u=2;u<=n;u++){
        for(int v=u+1;v<=n;v++){
            if(!rch[u][v])continue;
            for(int i=0,ui;i<3;i++){
                if(!(ui=f[u][i]))break;
                if(ui==v)continue;
                for(int j=0,vi;j<3;j++){
                    if(!(vi=f[v][j]))break;
                    //printf("1->%d->%d->%d->%d->1\n",ui,u,v,vi);
                    if(vi==u||ui==vi)continue;
                    max_s(ans,pts[ui]+pts[u]+pts[v]+pts[vi]);
                }
            }
        }
    }
    printf("%lld",ans);
    return 0;
}