#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = int(0); i < int((int)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const int inf = INT_MAX / 2 - 100;
namespace MaxFlow {
using CapType = int;
struct Edge {
  int to, rev;
  CapType cap;
};
vector<vector<Edge>> g;
vi itr, level;
void Init(int n) {
  g.assign(n, vector<Edge>());
  itr.assign(n, 0);
  level.assign(n, 0);
}
void AddEdge(int from, int to, CapType cap) {
  g[from].push_back({to, (int)g[to].size(), cap});
  g[to].push_back({from, (int)g[from].size() - 1, 0});
}
void bfs(int s) {
  fill(level.begin(), level.end(), -1);
  level[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto e : g[v])
      if (e.cap > 0 && level[e.to] == -1) {
        level[e.to] = level[v] + 1;
        q.push(e.to);
      }
  }
}
CapType dfs(int v, int t, CapType f) {
  if (v == t) return f;
  CapType res = 0;
  for (int& i = itr[v]; i < (int)g[v].size(); i++) {
    Edge& e = g[v][i];
    if (e.cap > 0 && level[e.to] == level[v] + 1) {
      CapType d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        g[e.to][e.rev].cap += d;
        res += d;
        f -= d;
        if (f <= 0) break;
      }
    }
  }
  return res;
}
CapType Calc(int s, int t) {
  CapType flow = 0;
  while (1) {
    bfs(s);
    if (level[t] == -1) return flow;
    fill(itr.begin(), itr.end(), 0);
    flow += dfs(s, t, inf);
  }
}
}  // namespace MaxFlow
const int Vmax = 610;
struct Edge {
  int to, cost;
};
vector<Edge> g[Vmax];
vi waf(int n, int root) {
  vi dist(n, inf);
  priority_queue<pi, vector<pi>, greater<pi>> pq;
  const auto Reach = [&](int v, int cost) {
    if (dist[v] > cost) {
      dist[v] = cost;
      pq.push(pi(cost, v));
    }
  };
  Reach(root, 0);
  while (!pq.empty()) {
    int c = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    for (auto e : g[v]) Reach(e.to, c + e.cost);
  }
  return dist;
}
signed main() {
  int v = read(), e = read(), n = read(), k = read();
  vi st(n);
  for (int i = int(0); i < int(n); i++) st[i] = read() - 1;
  for (int _ = int(0); _ < int(e); _++) {
    int a = read() - 1, b = read() - 1, c = read();
    g[a].push_back(Edge{b, c});
    g[b].push_back(Edge{a, c});
  }
  vector<vi> dss(n);
  for (int i = int(0); i < int(n); i++) dss[i] = waf(v, st[i]);
  int low = -1, up = 1731311 + 1;
  while (up - low > 1) {
    const int mid = (low + up) / 2;
    MaxFlow::Init(1 + n + v + 1);
    for (int i = int(0); i < int(n); i++) {
      MaxFlow::AddEdge(0, 1 + i, 1);
    }
    for (int i = int(0); i < int(v); i++) {
      MaxFlow::AddEdge(1 + n + i, 1 + n + v, 1);
    }
    for (int i = int(0); i < int(n); i++)
      for (int j = int(0); j < int(v); j++)
        if (dss[i][j] <= mid) {
          MaxFlow::AddEdge(1 + i, 1 + n + j, 1);
        }
    if (MaxFlow::Calc(0, 1 + n + v) >= k)
      up = mid;
    else
      low = mid;
  }
  if (up <= 1731311) {
    print(up);
  } else
    print(-1);
}

### 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>
using namespace std;
using ll = int64_t;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = int(0); i < int((int)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const int inf = INT_MAX / 2 - 100;
namespace MaxFlow {
using CapType = int;
struct Edge {
  int to, rev;
  CapType cap;
};
vector<vector<Edge>> g;
vi itr, level;
void Init(int n) {
  g.assign(n, vector<Edge>());
  itr.assign(n, 0);
  level.assign(n, 0);
}
void AddEdge(int from, int to, CapType cap) {
  g[from].push_back({to, (int)g[to].size(), cap});
  g[to].push_back({from, (int)g[from].size() - 1, 0});
}
void bfs(int s) {
  fill(level.begin(), level.end(), -1);
  level[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto e : g[v])
      if (e.cap > 0 && level[e.to] == -1) {
        level[e.to] = level[v] + 1;
        q.push(e.to);
      }
  }
}
CapType dfs(int v, int t, CapType f) {
  if (v == t) return f;
  CapType res = 0;
  for (int& i = itr[v]; i < (int)g[v].size(); i++) {
    Edge& e = g[v][i];
    if (e.cap > 0 && level[e.to] == level[v] + 1) {
      CapType d = dfs(e.to, t, min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        g[e.to][e.rev].cap += d;
        res += d;
        f -= d;
        if (f <= 0) break;
      }
    }
  }
  return res;
}
CapType Calc(int s, int t) {
  CapType flow = 0;
  while (1) {
    bfs(s);
    if (level[t] == -1) return flow;
    fill(itr.begin(), itr.end(), 0);
    flow += dfs(s, t, inf);
  }
}
}  // namespace MaxFlow
const int Vmax = 610;
struct Edge {
  int to, cost;
};
vector<Edge> g[Vmax];
vi waf(int n, int root) {
  vi dist(n, inf);
  priority_queue<pi, vector<pi>, greater<pi>> pq;
  const auto Reach = [&](int v, int cost) {
    if (dist[v] > cost) {
      dist[v] = cost;
      pq.push(pi(cost, v));
    }
  };
  Reach(root, 0);
  while (!pq.empty()) {
    int c = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    for (auto e : g[v]) Reach(e.to, c + e.cost);
  }
  return dist;
}
signed main() {
  int v = read(), e = read(), n = read(), k = read();
  vi st(n);
  for (int i = int(0); i < int(n); i++) st[i] = read() - 1;
  for (int _ = int(0); _ < int(e); _++) {
    int a = read() - 1, b = read() - 1, c = read();
    g[a].push_back(Edge{b, c});
    g[b].push_back(Edge{a, c});
  }
  vector<vi> dss(n);
  for (int i = int(0); i < int(n); i++) dss[i] = waf(v, st[i]);
  int low = -1, up = 1731311 + 1;
  while (up - low > 1) {
    const int mid = (low + up) / 2;
    MaxFlow::Init(1 + n + v + 1);
    for (int i = int(0); i < int(n); i++) {
      MaxFlow::AddEdge(0, 1 + i, 1);
    }
    for (int i = int(0); i < int(v); i++) {
      MaxFlow::AddEdge(1 + n + i, 1 + n + v, 1);
    }
    for (int i = int(0); i < int(n); i++)
      for (int j = int(0); j < int(v); j++)
        if (dss[i][j] <= mid) {
          MaxFlow::AddEdge(1 + i, 1 + n + j, 1);
        }
    if (MaxFlow::Calc(0, 1 + n + v) >= k)
      up = mid;
    else
      low = mid;
  }
  if (up <= 1731311) {
    print(up);
  } else
    print(-1);
}

```