Vacation Planning

Air Bovinia runs flights between the $N$ farms where the cows live ($1 \le N \le 20000$). $K$ of those farms are hubs ($1 \le K \le 200$, $K \le N$).

The airline currently offers $M$ one way flights ($1 \le M \le 20000$). Flight $i$ goes from farm $u_i$ to farm $v_i$ and costs $d_i$ dollars ($1 \le d_i \le 10000$). On every flight at least one of $u_i$ and $v_i$ is a hub. Two farms have at most one direct flight in a given direction, and no flight starts and ends at the same farm.

Bessie runs the ticket desk for Air Bovinia. While she was away chewing delicious hay for a few hours, $Q$ one way travel requests for the holiday vacations arrived ($1 \le Q \le 50000$). Request $i$ asks for a ticket from farm $a_i$ to farm $b_i$.

Decide for each request whether it can be fulfilled, and find its minimum cost when it can.

To keep the output small, print only how many requests can be fulfilled and the minimum total cost of fulfilling those requests. That total may not fit in a 32 bit integer.

• Line 1: the integers $N$, $M$, $K$, and $Q$.
• Lines 2 to $M + 1$: $u_i$, $v_i$, and $d_i$. ($1 \le u_i, v_i \le N$, $u_i \ne v_i$)
• Lines $M + 2$ to $M + K + 1$: each line holds the ID of one hub, between $1$ and $N$.
• Lines $M + K + 2$ to $M + K + Q + 1$: two numbers per line, a ticket request from farm $a_i$ to farm $b_i$. ($1 \le a_i, b_i \le N$, $a_i \ne b_i$)

• Line 1: the number of ticket requests that can be fulfilled.
• Line 2: the minimum total cost of fulfilling those requests.

In the example the first request can only travel farm 1 → 2 → 3 at a cost of 20. No flight leaves farm 3, so the second request cannot be fulfilled.