题目描述

Bovinia设计了连接N (1 < = N < = 20,000)个农场的航班。对于任何航班，指定了其中的k个农场作为枢纽。 (1 < = K <= 200 , K < = N)。 目前，共有M种单向航班（ 1 < = M < = 20,000 ），第i个航班从农场u_i至农场v_i花费d_i ( 1 < = d_i < =10,000 )美元。航班保证u_i或者v_i至少有一个是枢纽，任意两个农场至多只有一个航班，保证u_i≠v_i。 Bessie负责票务服务。共收到Q个度假请求，(1 < = Q < = 50,000)，其中第i个请求是从农场a_i至农场b_i 。请帮助她计算，每个请求是否满足 ，并计算：能满足的度假请求的最小费用总和。

输入格式

第1行：四个整数N,M,K,Q  第2 - M+1行：三个整数ui,vi,di  第M+2 - M+K+1行：枢纽的农场编号X (0<=X<=N)  第M+K+2..M+K+Q+1：两个整数，度假请求ai,bi

输出格式

第1行：能够满足的度假请求数 第2行：能满足的度假请求的最小费用总和

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

1
20
【样例解释】
第1个请求，航线设计为1->2->3,费用为20
第2个请求，无法满足

提示

没有写明提示

题目来源

Gold