Airline Hub Routing

We are given (N) farms (numbered 1 through (N), where (1 \leq N \leq 200)) and (M) directed routes connecting these farms. Each route from farm (u) to farm (v) costs (d) dollars ((1 \leq d \leq 10^6)). There are (K) designated hub farms (farms 1 through (K), with (1 \leq K \leq \min(100, N))).

The airline has (Q) flight requests. Each request consists of two integers (a) and (b), representing a request from farm (a) to farm (b). In order for a flight request to be feasible, the route must pass through at least one hub farm. Note that the hub can be the starting or the destination farm, and the route is allowed to visit the same farm multiple times.

The task is to determine two things:

1. The number of feasible flight requests.
2. The total minimum cost required to complete all feasible flight requests. For each flight request, if there exists a route from (a) to (b) passing through at least one hub, consider the minimum cost among such routes. If no such route exists, the request is not feasible.

The problem can be solved by first computing all pairs shortest paths (for example, using the Floyd–Warshall algorithm) and then, for each query, attempting to find a hub (h) ((1 \leq h \leq K)) such that the cost (\text{cost}(a, h) + \text{cost}(h, b)) is minimized. If the minimum cost remains infinite, the request is not feasible.

inputFormat

The input consists of multiple parts:

• The first line contains four space-separated integers: (N), (M), (K), (Q).
• The next (M) lines each contain three integers (u), (v), and (d), representing a directed route from farm (u) to farm (v) with cost (d).
• The following (Q) lines each contain two integers (a) and (b), representing a flight request from farm (a) to farm (b).

Constraints:

(1 \leq N \leq 200); (1 \leq M \leq 10,000); (1 \leq K \leq \min(100, N)); (1 \leq Q \leq 10,000); (1 \leq d \leq 1,000,000).

outputFormat

Output two integers separated by a space: the number of feasible flight requests and the total minimum cost required to complete them.

sample

4 4 2 3
1 3 10
3 2 5
2 4 7
1 4 100
1 4
3 4
4 1

2 22