smoothie-web Problems Contests Ranking About

# BSSPC 2019 P8 - Bayview's Music Department

## Problem Statement

The Bayview Music department is going to Ottawa! As such, magicalsoup is planning the trip, more specifically, the number of buses needed for trips between cities. There are $N$ ($1 \le N \le 20,000$) cities in the town of Ottawa. Among these $N$ cities, $K$ ($1 \le K \le 200, K \le N$) of them have been designated as tourist attractions. Currently, the coach bus company offers $M$ ($1 \le M \le 20,000$) one-way trips, where road $i$ that travels from city $u_i$ to city $v_i$ and costs the music department $d_i$ ($1 \le di \le 10,000$) amount of money. For each of these trips, at least one of $u_i$ and $v_i$ is a tourist attraction. There is at most one direct trip between cities in any given direction, and no trip starts and ends at the same city.

magicalsoup has been given $Q$ ($1 \le Q \le 50,000$) one way trips by Dr.Z. Where the $i$-th request is from city $a_i$ to city $b_i$. Can you help magicalsoup figure out the total number of trips that are possible, and the minimum total cost for them (the music department is lacking some money).

## Input Specification

The first line contains 4 integers $N$, $M$, $K$, and $Q$.

Each of the following $M$ lines contains 3 integers $u_i$, $v_i$ and $d_i$, there is a road between $u_i$ and $v_i$ with cost of $d_i$.

Each of the following $K$ lines contains an integer $x$, the tourist attraction cities.

Each of the following $Q$ lines contains two integers $a_i$ and $b_i$, indicating a trip from city $a_i$ to city $b_i$.

## Output Specification

The first line contains one integer, the number of trips that are possible.

The second line contains one integer, the minimum total cost of fulfilling the possible trips.

## Sample Input

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1


## Sample Output

1
20


## Explanation

For the first request, the only possible route is $1 \rightarrow 2 \rightarrow 3$, costing $20$. There are no trips leaving from city $3$, so the trip is not possible.