#include <bits/stdc++.h>
using namespace std;
int n, m, s, k, x, y, z, S, T, sl, fh, st[1010], cur[1010], dep[1010],
    f[610][610];
int t, head[1010], to[1000010], nxt[1000010], val[1000010];
queue<int> q;
int rd() {
  sl = 0;
  fh = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') sl = sl * 10 + ch - '0', ch = getchar();
  return sl * fh;
}
void add(int u, int v, int w) {
  to[t] = v;
  val[t] = w;
  nxt[t] = head[u];
  head[u] = t++;
}
bool bfs() {
  while (!q.empty()) q.pop();
  memset(dep, 0, sizeof(dep));
  q.push(S);
  dep[S] = 1;
  int u, v;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = head[u]; i != -1; i = nxt[i])
      if (!dep[v = to[i]] && val[i] > 0) {
        dep[v] = dep[u] + 1;
        if (v == T) return 1;
        q.push(v);
      }
  }
  return 0;
}
int dfs(int u, int f) {
  if (f <= 0) return 0;
  if (u == T) return f;
  int v, q = 0, tmp;
  for (int &i = cur[u]; i != -1; i = nxt[i])
    if (dep[v = to[i]] == dep[u] + 1) {
      tmp = dfs(v, min(f, val[i]));
      if (!tmp) continue;
      f -= tmp;
      q += tmp;
      val[i] -= tmp;
      val[i ^ 1] += tmp;
      if (!f) return q;
    }
  return q;
}
bool check(int len) {
  memset(head, -1, sizeof(head));
  t = 0;
  for (int i = 1; i <= s; ++i) add(S, i, 1), add(i, S, 0);
  for (int i = 1; i <= n; ++i) add(s + i, T, 1), add(T, s + i, 0);
  for (int i = 1; i <= s; ++i)
    for (int j = 1; j <= n; ++j)
      if (f[st[i]][j] <= len) add(i, j + s, 1), add(j + s, i, 0);
  int sum, ans = 0;
  while (bfs()) {
    for (int i = 0; i <= s + n + 1; ++i) cur[i] = head[i];
    while (sum = dfs(S, 0x7fffffff)) ans += sum;
  }
  return ans >= k;
}
int main() {
  n = rd();
  m = rd();
  s = rd();
  k = rd();
  memset(f, 127 / 3, sizeof(f));
  for (int i = 1; i <= s; ++i) st[i] = rd();
  for (int i = 1; i <= m; ++i) {
    x = rd();
    y = rd();
    z = rd();
    f[x][y] = f[y][x] = min(f[x][y], z);
  }
  for (int i = 1; i <= n; ++i) f[i][i] = 0;
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      if (i != k)
        for (int j = 1; j <= n; ++j)
          if (i != j && j != k) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
  int mid, ans = -1, l = 0, r = 1731311;
  S = 0, T = s + n + 1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid))
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
int n, m, s, k, x, y, z, S, T, sl, fh, st[1010], cur[1010], dep[1010],
    f[610][610];
int t, head[1010], to[1000010], nxt[1000010], val[1000010];
queue<int> q;
int rd() {
  sl = 0;
  fh = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') sl = sl * 10 + ch - '0', ch = getchar();
  return sl * fh;
}
void add(int u, int v, int w) {
  to[t] = v;
  val[t] = w;
  nxt[t] = head[u];
  head[u] = t++;
}
bool bfs() {
  while (!q.empty()) q.pop();
  memset(dep, 0, sizeof(dep));
  q.push(S);
  dep[S] = 1;
  int u, v;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = head[u]; i != -1; i = nxt[i])
      if (!dep[v = to[i]] && val[i] > 0) {
        dep[v] = dep[u] + 1;
        if (v == T) return 1;
        q.push(v);
      }
  }
  return 0;
}
int dfs(int u, int f) {
  if (f <= 0) return 0;
  if (u == T) return f;
  int v, q = 0, tmp;
  for (int &i = cur[u]; i != -1; i = nxt[i])
    if (dep[v = to[i]] == dep[u] + 1) {
      tmp = dfs(v, min(f, val[i]));
      if (!tmp) continue;
      f -= tmp;
      q += tmp;
      val[i] -= tmp;
      val[i ^ 1] += tmp;
      if (!f) return q;
    }
  return q;
}
bool check(int len) {
  memset(head, -1, sizeof(head));
  t = 0;
  for (int i = 1; i <= s; ++i) add(S, i, 1), add(i, S, 0);
  for (int i = 1; i <= n; ++i) add(s + i, T, 1), add(T, s + i, 0);
  for (int i = 1; i <= s; ++i)
    for (int j = 1; j <= n; ++j)
      if (f[st[i]][j] <= len) add(i, j + s, 1), add(j + s, i, 0);
  int sum, ans = 0;
  while (bfs()) {
    for (int i = 0; i <= s + n + 1; ++i) cur[i] = head[i];
    while (sum = dfs(S, 0x7fffffff)) ans += sum;
  }
  return ans >= k;
}
int main() {
  n = rd();
  m = rd();
  s = rd();
  k = rd();
  memset(f, 127 / 3, sizeof(f));
  for (int i = 1; i <= s; ++i) st[i] = rd();
  for (int i = 1; i <= m; ++i) {
    x = rd();
    y = rd();
    z = rd();
    f[x][y] = f[y][x] = min(f[x][y], z);
  }
  for (int i = 1; i <= n; ++i) f[i][i] = 0;
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      if (i != k)
        for (int j = 1; j <= n; ++j)
          if (i != j && j != k) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
  int mid, ans = -1, l = 0, r = 1731311;
  S = 0, T = s + n + 1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid))
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}

```