#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
struct Edge {
  int to, rev, f, cap;
};
class Dinic {
 public:
  int dist[1000], q[1000], work[1000], src, dest;
  vector<Edge> graph[1000];
  void init(int sz) {
    for (int i = (0); i < (sz + 1); i++) graph[i].clear();
  }
  void clearFlow(int sz) {
    for (int i = (0); i < (sz + 1); i++) {
      for (int j = (0); j < (graph[i].size()); j++) graph[i][j].f = 0;
    }
  }
  void addEdge(int s, int t, int cap) {
    Edge a = {t, (int)graph[t].size(), 0, cap};
    Edge b = {s, (int)graph[s].size(), 0, 0};
    graph[s].push_back(a);
    graph[t].push_back(b);
  }
  bool bfs() {
    memset(dist, -1, sizeof(dist));
    dist[src] = 0;
    int qt = 0;
    q[qt++] = src;
    for (int qh = 0; qh < qt; qh++) {
      int u = q[qh];
      for (int j = 0; j < graph[u].size(); j++) {
        Edge &e = graph[u][j];
        int v = e.to;
        if (dist[v] < 0 && e.f < e.cap) {
          dist[v] = dist[u] + 1;
          q[qt++] = v;
        }
      }
    }
    return dist[dest] >= 0;
  }
  int dfs(int u, int f) {
    if (u == dest) return f;
    for (int &i = work[u]; i < (int)graph[u].size(); i++) {
      Edge &e = graph[u][i];
      if (e.cap <= e.f) continue;
      int v = e.to;
      if (dist[v] == dist[u] + 1) {
        int df = dfs(v, min(f, e.cap - e.f));
        if (df > 0) {
          e.f += df;
          graph[v][e.rev].f -= df;
          return df;
        }
      }
    }
    return 0;
  }
  int maxFlow(int _src, int _dest) {
    src = _src;
    dest = _dest;
    int result = 0;
    while (bfs()) {
      fill(work, work + 1000, 0);
      while (int delta = dfs(src, 2000000000)) result += delta;
    }
    return result;
  }
} network;
int v, e, n, k, teams[202], a, b, t;
vector<pair<int, int> > graph[606];
int dist[606][606], src = 0, sink = 801;
const int inf = 1061109567;
void dijkstra(int src) {
  priority_queue<pair<int, int> > pq;
  pq.push({0, src});
  memset(dist[src], 63, sizeof(dist[src]));
  dist[src][src] = 0;
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    for (auto it : graph[u]) {
      if (dist[src][u] + it.second < dist[src][it.first]) {
        dist[src][it.first] = dist[src][u] + it.second;
        pq.push({-dist[src][it.first], it.first});
      }
    }
  }
}
void buildNetwork(int limit) {
  for (int i = (1); i < (v + 1); i++) {
    network.addEdge(src, i, 1);
    for (int j = (1); j < (n + 1); j++) {
      if (dist[i][teams[j]] <= limit) {
        network.addEdge(i, j + v, 1);
      }
    }
  }
  for (int j = (1); j < (n + 1); j++) network.addEdge(j + v, sink, 1);
}
bool check(int limit) {
  network.init(sink + 5);
  buildNetwork(limit);
  int flow = network.maxFlow(src, sink);
  return flow >= k;
}
int main() {
  int test, cases = 1;
  scanf("%d%d%d%d", &v, &e, &n, &k);
  for (int i = (1); i < (n + 1); i++) {
    scanf("%d", &teams[i]);
  }
  for (int i = (1); i < (e + 1); i++) {
    scanf("%d%d%d", &a, &b, &t);
    graph[a].push_back({b, t});
    graph[b].push_back({a, t});
  }
  for (int i = (1); i < (v + 1); i++) dijkstra(i);
  int low = 0, high = 1731311, ans = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (check(mid)) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
struct Edge {
  int to, rev, f, cap;
};
class Dinic {
 public:
  int dist[1000], q[1000], work[1000], src, dest;
  vector<Edge> graph[1000];
  void init(int sz) {
    for (int i = (0); i < (sz + 1); i++) graph[i].clear();
  }
  void clearFlow(int sz) {
    for (int i = (0); i < (sz + 1); i++) {
      for (int j = (0); j < (graph[i].size()); j++) graph[i][j].f = 0;
    }
  }
  void addEdge(int s, int t, int cap) {
    Edge a = {t, (int)graph[t].size(), 0, cap};
    Edge b = {s, (int)graph[s].size(), 0, 0};
    graph[s].push_back(a);
    graph[t].push_back(b);
  }
  bool bfs() {
    memset(dist, -1, sizeof(dist));
    dist[src] = 0;
    int qt = 0;
    q[qt++] = src;
    for (int qh = 0; qh < qt; qh++) {
      int u = q[qh];
      for (int j = 0; j < graph[u].size(); j++) {
        Edge &e = graph[u][j];
        int v = e.to;
        if (dist[v] < 0 && e.f < e.cap) {
          dist[v] = dist[u] + 1;
          q[qt++] = v;
        }
      }
    }
    return dist[dest] >= 0;
  }
  int dfs(int u, int f) {
    if (u == dest) return f;
    for (int &i = work[u]; i < (int)graph[u].size(); i++) {
      Edge &e = graph[u][i];
      if (e.cap <= e.f) continue;
      int v = e.to;
      if (dist[v] == dist[u] + 1) {
        int df = dfs(v, min(f, e.cap - e.f));
        if (df > 0) {
          e.f += df;
          graph[v][e.rev].f -= df;
          return df;
        }
      }
    }
    return 0;
  }
  int maxFlow(int _src, int _dest) {
    src = _src;
    dest = _dest;
    int result = 0;
    while (bfs()) {
      fill(work, work + 1000, 0);
      while (int delta = dfs(src, 2000000000)) result += delta;
    }
    return result;
  }
} network;
int v, e, n, k, teams[202], a, b, t;
vector<pair<int, int> > graph[606];
int dist[606][606], src = 0, sink = 801;
const int inf = 1061109567;
void dijkstra(int src) {
  priority_queue<pair<int, int> > pq;
  pq.push({0, src});
  memset(dist[src], 63, sizeof(dist[src]));
  dist[src][src] = 0;
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    for (auto it : graph[u]) {
      if (dist[src][u] + it.second < dist[src][it.first]) {
        dist[src][it.first] = dist[src][u] + it.second;
        pq.push({-dist[src][it.first], it.first});
      }
    }
  }
}
void buildNetwork(int limit) {
  for (int i = (1); i < (v + 1); i++) {
    network.addEdge(src, i, 1);
    for (int j = (1); j < (n + 1); j++) {
      if (dist[i][teams[j]] <= limit) {
        network.addEdge(i, j + v, 1);
      }
    }
  }
  for (int j = (1); j < (n + 1); j++) network.addEdge(j + v, sink, 1);
}
bool check(int limit) {
  network.init(sink + 5);
  buildNetwork(limit);
  int flow = network.maxFlow(src, sink);
  return flow >= k;
}
int main() {
  int test, cases = 1;
  scanf("%d%d%d%d", &v, &e, &n, &k);
  for (int i = (1); i < (n + 1); i++) {
    scanf("%d", &teams[i]);
  }
  for (int i = (1); i < (e + 1); i++) {
    scanf("%d%d%d", &a, &b, &t);
    graph[a].push_back({b, t});
    graph[b].push_back({a, t});
  }
  for (int i = (1); i < (v + 1); i++) dijkstra(i);
  int low = 0, high = 1731311, ans = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (check(mid)) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  cout << ans << "\n";
  return 0;
}

```