https://pintia.cn/problem-sets/1556843855285559296/exam/problems/type/7?problemSetProblemId=1556843936151740418&page=0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define int long long
#define INF 0x3f3f3f3f
#define endl '\n'
#define N 200010
const int mod = 1e9 + 7;


int n, m, k, p;

struct node {
    int no, bu, ww;
};

map<int, int> mp;

vector<int> g[N];
int vis[N];
int w[N];
int s, t;
int res = 0, mi = 0x3f3f3f3f;

void dfs() {
    queue<node> q;

    node t1;
    t1.no = s;
    t1.bu = 0;
    t1.ww = 0;


    if (p == 1)t1.ww = w[s];

    q.push(t1);

    while (q.size()) {
        auto to = q.front();
        q.pop();
        vis[to.no] = 1;

        if (to.bu > mi)break;
        if (to.no == t) {
            res = max(res, to.ww);
            mi = to.bu;

            continue ;
        }

        for (auto u : g[to.no]) {

            if (!vis[u] || u == t) {
                vis[u] = 1;
                int no = u;
                int st = to.bu + 1;
                int ww = to.ww;
                if (st % k + 1 == p) ww += w[u];
                q.push({no, st, ww});

            }
        }
    }
}
void solve() {
    cin >> n >> m >> k >> p;

    for (int i = 1; i <= n; i++)cin >> w[i];



    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        if (u != v) {

            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    cin >> s >> t;

    dfs();
    cout << res << endl;
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while (T --)

        solve();

    return 0;
}