smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2019 P8 - Bayview's Music Department

data_usage Points
timer Time Limit
linear_scale Memory Limit

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 NN (1N20,0001 \le N \le 20,000) cities in the town of Ottawa. Among these NN cities, KK (1K200,KN1 \le K \le 200, K \le N) of them have been designated as tourist attractions. Currently, the coach bus company offers MM (1M20,0001 \le M \le 20,000) one-way trips, where road ii that travels from city uiu_i to city viv_i and costs the music department did_i (1di10,0001 \le di \le 10,000) amount of money. For each of these trips, at least one of uiu_i and viv_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 QQ (1Q50,0001 \le Q \le 50,000) one way trips by Dr.Z. Where the ii-th request is from city aia_i to city bib_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 NN, MM, KK, and QQ.

Each of the following MM lines contains 3 integers uiu_i, viv_i and did_i, there is a road between uiu_i and viv_i with cost of did_i.

Each of the following KK lines contains an integer xx, the tourist attraction cities.

Each of the following QQ lines contains two integers aia_i and bib_i, indicating a trip from city aia_i to city bib_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
1 3
3 1

Sample Output



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