#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
template <class C>
struct MaxFlow {
  C flow;
  V<char> dual;
};
template <class C, class E>
struct MF_EXEC {
  static constexpr C INF = numeric_limits<C>::max();
  C eps;
  VV<E>& g;
  int s, t;
  V<int> level, iter;
  C dfs(int v, C f) {
    if (v == t) return f;
    C res = 0;
    for (int& i = iter[v]; i < int(g[v].size()); i++) {
      E& e = g[v][i];
      if (e.cap <= eps || level[v] >= level[e.to]) continue;
      C d = dfs(e.to, min(f, e.cap));
      e.cap -= d;
      g[e.to][e.rev].cap += d;
      res += d;
      f -= d;
      if (f == 0) break;
    }
    return res;
  }
  MaxFlow<C> info;
  MF_EXEC(VV<E>& _g, int _s, int _t, C _eps) : eps(_eps), g(_g), s(_s), t(_t) {
    int N = int(g.size());
    C& flow = (info.flow = 0);
    while (true) {
      queue<int> que;
      level = V<int>(N, -1);
      level[s] = 0;
      que.push(s);
      while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (E e : g[v]) {
          if (e.cap <= eps || level[e.to] >= 0) continue;
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
      }
      if (level[t] == -1) break;
      iter = V<int>(N, 0);
      while (true) {
        C f = dfs(s, INF);
        if (!f) break;
        flow += f;
      }
    }
    for (int i = 0; i < N; i++) info.dual.push_back(level[i] == -1);
  }
};
template <class C, class E>
MaxFlow<C> get_mf(VV<E>& g, int s, int t, C eps) {
  return MF_EXEC<C, E>(g, s, t, eps).info;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;
  int v, e, n, k;
  cin >> v >> e >> n >> k;
  V<int> pos(n);
  for (int i = 0; i < n; i++) {
    cin >> pos[i];
    pos[i]--;
  }
  VV<int> dist(v, V<int>(v, TEN(9)));
  for (int i = 0; i < v; i++) dist[i][i] = 0;
  for (int i = 0; i < e; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    dist[a][b] = min(dist[a][b], c);
    dist[b][a] = min(dist[b][a], c);
  }
  for (int k = 0; k < v; k++) {
    for (int i = 0; i < v; i++) {
      for (int j = 0; j < v; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  int lw = -1, up = 1731312;
  while (up - lw > 1) {
    int md = (lw + up) / 2;
    struct E {
      int to, rev, cap;
    };
    VV<E> g(n + v + 2);
    int sv = n + v, tv = sv + 1;
    auto add_edge = [&](int from, int to, int cap) {
      g[from].push_back(E{to, int(g[to].size()), cap});
      g[to].push_back(E{from, int(g[from].size()) - 1, 0});
    };
    for (int p = 0; p < n; p++) add_edge(sv, p, 1);
    for (int j = 0; j < v; j++) add_edge(n + j, tv, 1);
    for (int p = 0; p < n; p++) {
      int i = pos[p];
      for (int j = 0; j < v; j++) {
        if (dist[i][j] <= md) add_edge(p, n + j, 1);
      }
    }
    if (get_mf(g, sv, tv, 0).flow < k)
      lw = md;
    else
      up = md;
  }
  if (up == 1731312)
    cout << -1 << endl;
  else
    cout << up << endl;
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities.

After exploring the map of Serbia for a while, the competitors came up with the following facts: the country has V cities which are indexed with numbers from 1 to V, and there are E bi-directional roads that connect the cites. Each road has a weight (the time needed to cross that road). There are N teams at the Bubble Cup and the competitors came up with the following plan: each of the N teams will start their journey in one of the V cities, and some of the teams share the starting position.

They want to find the shortest time T, such that every team can move in these T minutes, and the number of different cities they end up in is at least K (because they will only get to know the cities they end up in). A team doesn't have to be on the move all the time, if they like it in a particular city, they can stay there and wait for the time to pass.

Please help the competitors to determine the shortest time T so it's possible for them to end up in at least K different cities or print -1 if that is impossible no matter how they move.

Note that there can exist multiple roads between some cities.

Input

The first line contains four integers: V, E, N and K (1 ≤ V ≤ 600, 1 ≤ E ≤ 20000, 1 ≤ N ≤ min(V, 200), 1 ≤ K ≤ N), number of cities, number of roads, number of teams and the smallest number of different cities they need to end up in, respectively.

The second line contains N integers, the cities where the teams start their journey.

Next E lines contain information about the roads in following format: Ai Bi Ti (1 ≤ Ai, Bi ≤ V, 1 ≤ Ti ≤ 10000), which means that there is a road connecting cities Ai and Bi, and you need Ti minutes to cross that road.

Output

Output a single integer that represents the minimal time the teams can move for, such that they end up in at least K different cities or output -1 if there is no solution.

If the solution exists, result will be no greater than 1731311.

Example

Input

6 7 5 4
5 5 2 2 5
1 3 3
1 5 2
1 6 5
2 5 4
2 6 7
3 4 11
3 5 3


Output

3

Note

Three teams start from city 5, and two teams start from city 2. If they agree to move for 3 minutes, one possible situation would be the following: Two teams in city 2, one team in city 5, one team in city 3 , and one team in city 1. And we see that there are four different cities the teams end their journey at.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
template <class C>
struct MaxFlow {
  C flow;
  V<char> dual;
};
template <class C, class E>
struct MF_EXEC {
  static constexpr C INF = numeric_limits<C>::max();
  C eps;
  VV<E>& g;
  int s, t;
  V<int> level, iter;
  C dfs(int v, C f) {
    if (v == t) return f;
    C res = 0;
    for (int& i = iter[v]; i < int(g[v].size()); i++) {
      E& e = g[v][i];
      if (e.cap <= eps || level[v] >= level[e.to]) continue;
      C d = dfs(e.to, min(f, e.cap));
      e.cap -= d;
      g[e.to][e.rev].cap += d;
      res += d;
      f -= d;
      if (f == 0) break;
    }
    return res;
  }
  MaxFlow<C> info;
  MF_EXEC(VV<E>& _g, int _s, int _t, C _eps) : eps(_eps), g(_g), s(_s), t(_t) {
    int N = int(g.size());
    C& flow = (info.flow = 0);
    while (true) {
      queue<int> que;
      level = V<int>(N, -1);
      level[s] = 0;
      que.push(s);
      while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (E e : g[v]) {
          if (e.cap <= eps || level[e.to] >= 0) continue;
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
      }
      if (level[t] == -1) break;
      iter = V<int>(N, 0);
      while (true) {
        C f = dfs(s, INF);
        if (!f) break;
        flow += f;
      }
    }
    for (int i = 0; i < N; i++) info.dual.push_back(level[i] == -1);
  }
};
template <class C, class E>
MaxFlow<C> get_mf(VV<E>& g, int s, int t, C eps) {
  return MF_EXEC<C, E>(g, s, t, eps).info;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;
  int v, e, n, k;
  cin >> v >> e >> n >> k;
  V<int> pos(n);
  for (int i = 0; i < n; i++) {
    cin >> pos[i];
    pos[i]--;
  }
  VV<int> dist(v, V<int>(v, TEN(9)));
  for (int i = 0; i < v; i++) dist[i][i] = 0;
  for (int i = 0; i < e; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    dist[a][b] = min(dist[a][b], c);
    dist[b][a] = min(dist[b][a], c);
  }
  for (int k = 0; k < v; k++) {
    for (int i = 0; i < v; i++) {
      for (int j = 0; j < v; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  int lw = -1, up = 1731312;
  while (up - lw > 1) {
    int md = (lw + up) / 2;
    struct E {
      int to, rev, cap;
    };
    VV<E> g(n + v + 2);
    int sv = n + v, tv = sv + 1;
    auto add_edge = [&](int from, int to, int cap) {
      g[from].push_back(E{to, int(g[to].size()), cap});
      g[to].push_back(E{from, int(g[from].size()) - 1, 0});
    };
    for (int p = 0; p < n; p++) add_edge(sv, p, 1);
    for (int j = 0; j < v; j++) add_edge(n + j, tv, 1);
    for (int p = 0; p < n; p++) {
      int i = pos[p];
      for (int j = 0; j < v; j++) {
        if (dist[i][j] <= md) add_edge(p, n + j, 1);
      }
    }
    if (get_mf(g, sv, tv, 0).flow < k)
      lw = md;
    else
      up = md;
  }
  if (up == 1731312)
    cout << -1 << endl;
  else
    cout << up << endl;
  return 0;
}

```