Yuki is a magical girl and she has the ability to active portals.

The country Yuki lives in has \(n\) cities and \(m\) roads at certain distances. The cities are numbered from \(1\) to \(n\) and all the roads are unidirectional, that is a road from \(u\) to \(v\) cannot be passed from \(v\) to \(u\). Also, there are \(p\) portals in the country, each of them connects two cities unidirectional with no distance. Since Yuki doesn’t grasp magic thoroughly, she can active at most \(k\) portals.

Now Yuki is curious about what is the minimum distance between \(S\) and \(T\) if she actives at most \(k\) portals.

The first line contains four integers: \(n\), \(m\), \(p\) and \(k\) \((1\leq n,m,p\leq 50\ 000,0\leq k\leq10)\) — the number of cities, roads, portals and the number of portals Yuki can active at most.

Each of the next \(m\) lines contains three integers: \(u\), \(v\) and \(w\) \((1 \leq u,\ v\leq n,1\leq w\leq 1\ 000\ 000)\), meaning that there is a unidirectional road from city \(u\) to city \(v\) at distance \(w\).

Each of the next \(p\) lines contains two integer: \(u\) and \(v\) \((1 \leq u,\ v\leq n)\), meaning that there is an inactive portal from city \(u\) to city \(v\). Please note that when it is active, Yuki can only be teleported from city \(u\) to \(v\) unidirectional.

The last line contains two integers: \(S\) and \(T\) \((1\leq S,T\leq n)\) — the origin and destination.

Print one line with the result — the minimum distance between \(S\) and \(T\).

5 6 3 1
1 3 4
1 2 2
3 5 6
2 4 3
3 4 1
4 5 2
2 3
1 4
1 2
1 5

2