#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T sqr(const T &x) {
  return x * x;
}
inline long long sqr(int x) { return sqr<long long>(x); }
template <class T>
T binpow(const T &a, long long n) {
  return n == 0 ? 1 : sqr(binpow(a, n / 2)) * (n % 2 ? a : 1);
}
long long binpow(long long a, long long n, long long modulo) {
  return n == 0 ? 1
                : sqr(binpow(a, n / 2, modulo)) % modulo * (n % 2 ? a : 1) %
                      modulo;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
inline long long gcd(long long a, long long b) { return gcd(a, b, a, b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long llrand() {
  const long long lsbToFill = (sizeof(long long) << 3) - 1;
  const long long bitsFilledInIteration = __builtin_popcountll(RAND_MAX);
  long long number = 0;
  for (long long lsbFilled = 0; lsbFilled <= lsbToFill;
       lsbFilled += bitsFilledInIteration) {
    number ^= (((long long)rand()) << lsbFilled);
  }
  return number & numeric_limits<long long>::max();
}
struct Edge {
  int u, v;
  long long cap, flow;
  Edge() {}
  Edge(int u, int v, long long cap) : u(u), v(v), cap(cap), flow(0) {}
};
struct Dinic {
  int N;
  vector<Edge> E;
  vector<vector<int>> g;
  vector<int> d, pt;
  Dinic(int N) : N(N), E(0), g(N), d(N), pt(N) {}
  void AddEdge(int u, int v, long long cap) {
    if (u != v) {
      E.emplace_back(Edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(Edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }
  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      for (int k : g[u]) {
        Edge &e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }
  long long DFS(int u, int T, long long flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int &i = pt[u]; i < g[u].size(); ++i) {
      Edge &e = E[g[u][i]];
      Edge &oe = E[g[u][i] ^ 1];
      if (d[e.v] == d[e.u] + 1) {
        long long amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (long long pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  long long MaxFlow(int S, int T) {
    long long total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (long long flow = DFS(S, T)) total += flow;
    }
    return total;
  }
};
vector<long long> Dijkstra(const vector<list<pair<int, long long>>> &g, int s) {
  vector<long long> dist(int((g).size()),
                         numeric_limits<long long>::max() / 2LL);
  priority_queue<pair<long long, int>> q;
  dist[s] = 0;
  q.emplace(-0, s);
  while (!q.empty()) {
    while (q.top().first > dist[q.top().second]) {
      q.pop();
    }
    int v = q.top().second;
    q.pop();
    for (const auto &cw : g[v]) {
      if (dist[v] + cw.second < dist[cw.first]) {
        dist[cw.first] = dist[v] + cw.second;
        q.emplace(-dist[cw.first], cw.first);
      }
    }
  }
  return dist;
}
int n, v;
int k;
vector<vector<long long>> dist;
bool check(int middle) {
  int s = n + v;
  int t = s + 1;
  Dinic dinic(t + 1);
  for (int i = (0); i < (n); ++i) {
    dinic.AddEdge(s, i, 1);
  }
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (v); ++j) {
      if (dist[i][j] <= middle) {
        dinic.AddEdge(i, n + j, 1);
      }
    }
  }
  for (int j = (0); j < (v); ++j) {
    dinic.AddEdge(n + j, t, 1);
  }
  long long flow = dinic.MaxFlow(s, t);
  return flow >= k;
}
struct BinarySearchIterator
    : public std::iterator<std::forward_iterator_tag, bool> {
  int value;
  typename iterator_traits<BinarySearchIterator>::difference_type operator-(
      const BinarySearchIterator &it) const {
    return value - it.value;
  }
  BinarySearchIterator &operator++() {
    ++value;
    return *this;
  }
  bool operator!=(const BinarySearchIterator &it) const {
    return value != it.value;
  }
  bool operator*() const { return check(value); }
};
int main(int argc, const char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  srand((unsigned int)time(NULL));
  int e;
  while (cin >> v >> e >> n >> k) {
    vector<int> s(n);
    for (int i = (0); i < (n); ++i) {
      cin >> s[i];
      --s[i];
    }
    vector<list<pair<int, long long>>> g(v);
    for (int i = (0); i < (e); ++i) {
      int a, b;
      long long t;
      cin >> a >> b >> t;
      --a;
      --b;
      g[a].emplace_back(b, t);
      g[b].emplace_back(a, t);
    }
    dist.resize(n);
    for (int i = (0); i < (n); ++i) {
      dist[i] = Dijkstra(g, s[i]);
    }
    BinarySearchIterator left, right;
    left.value = 0;
    right.value = 1731311 + 1;
    int answer = lower_bound(left, right, true).value;
    cout << (1731311 < answer ? -1 : answer) << endl;
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
template <class T>
inline T sqr(const T &x) {
  return x * x;
}
inline long long sqr(int x) { return sqr<long long>(x); }
template <class T>
T binpow(const T &a, long long n) {
  return n == 0 ? 1 : sqr(binpow(a, n / 2)) * (n % 2 ? a : 1);
}
long long binpow(long long a, long long n, long long modulo) {
  return n == 0 ? 1
                : sqr(binpow(a, n / 2, modulo)) % modulo * (n % 2 ? a : 1) %
                      modulo;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
inline long long gcd(long long a, long long b) { return gcd(a, b, a, b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long llrand() {
  const long long lsbToFill = (sizeof(long long) << 3) - 1;
  const long long bitsFilledInIteration = __builtin_popcountll(RAND_MAX);
  long long number = 0;
  for (long long lsbFilled = 0; lsbFilled <= lsbToFill;
       lsbFilled += bitsFilledInIteration) {
    number ^= (((long long)rand()) << lsbFilled);
  }
  return number & numeric_limits<long long>::max();
}
struct Edge {
  int u, v;
  long long cap, flow;
  Edge() {}
  Edge(int u, int v, long long cap) : u(u), v(v), cap(cap), flow(0) {}
};
struct Dinic {
  int N;
  vector<Edge> E;
  vector<vector<int>> g;
  vector<int> d, pt;
  Dinic(int N) : N(N), E(0), g(N), d(N), pt(N) {}
  void AddEdge(int u, int v, long long cap) {
    if (u != v) {
      E.emplace_back(Edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(Edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }
  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      for (int k : g[u]) {
        Edge &e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }
  long long DFS(int u, int T, long long flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int &i = pt[u]; i < g[u].size(); ++i) {
      Edge &e = E[g[u][i]];
      Edge &oe = E[g[u][i] ^ 1];
      if (d[e.v] == d[e.u] + 1) {
        long long amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (long long pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  long long MaxFlow(int S, int T) {
    long long total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (long long flow = DFS(S, T)) total += flow;
    }
    return total;
  }
};
vector<long long> Dijkstra(const vector<list<pair<int, long long>>> &g, int s) {
  vector<long long> dist(int((g).size()),
                         numeric_limits<long long>::max() / 2LL);
  priority_queue<pair<long long, int>> q;
  dist[s] = 0;
  q.emplace(-0, s);
  while (!q.empty()) {
    while (q.top().first > dist[q.top().second]) {
      q.pop();
    }
    int v = q.top().second;
    q.pop();
    for (const auto &cw : g[v]) {
      if (dist[v] + cw.second < dist[cw.first]) {
        dist[cw.first] = dist[v] + cw.second;
        q.emplace(-dist[cw.first], cw.first);
      }
    }
  }
  return dist;
}
int n, v;
int k;
vector<vector<long long>> dist;
bool check(int middle) {
  int s = n + v;
  int t = s + 1;
  Dinic dinic(t + 1);
  for (int i = (0); i < (n); ++i) {
    dinic.AddEdge(s, i, 1);
  }
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (v); ++j) {
      if (dist[i][j] <= middle) {
        dinic.AddEdge(i, n + j, 1);
      }
    }
  }
  for (int j = (0); j < (v); ++j) {
    dinic.AddEdge(n + j, t, 1);
  }
  long long flow = dinic.MaxFlow(s, t);
  return flow >= k;
}
struct BinarySearchIterator
    : public std::iterator<std::forward_iterator_tag, bool> {
  int value;
  typename iterator_traits<BinarySearchIterator>::difference_type operator-(
      const BinarySearchIterator &it) const {
    return value - it.value;
  }
  BinarySearchIterator &operator++() {
    ++value;
    return *this;
  }
  bool operator!=(const BinarySearchIterator &it) const {
    return value != it.value;
  }
  bool operator*() const { return check(value); }
};
int main(int argc, const char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  srand((unsigned int)time(NULL));
  int e;
  while (cin >> v >> e >> n >> k) {
    vector<int> s(n);
    for (int i = (0); i < (n); ++i) {
      cin >> s[i];
      --s[i];
    }
    vector<list<pair<int, long long>>> g(v);
    for (int i = (0); i < (e); ++i) {
      int a, b;
      long long t;
      cin >> a >> b >> t;
      --a;
      --b;
      g[a].emplace_back(b, t);
      g[b].emplace_back(a, t);
    }
    dist.resize(n);
    for (int i = (0); i < (n); ++i) {
      dist[i] = Dijkstra(g, s[i]);
    }
    BinarySearchIterator left, right;
    left.value = 0;
    right.value = 1731311 + 1;
    int answer = lower_bound(left, right, true).value;
    cout << (1731311 < answer ? -1 : answer) << endl;
  }
  return 0;
}

```