题目描述

有${N(1 <= N <= 200)}$个农场，用${1..N}$编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场${1..K}$中的农场作为枢纽${(1 <= K <= 100, K <= N)}$。

当前共有${M (1 <= M <= 10,000)}$条单向航线连接这些农场，从农场${u_i }$到农场 ${v_i, }$将花费 ${d_i}$美元。${(1 <= d_i <= 1,000,000).}$

航空公司最近收到${Q (1 <= Q <= 10,000)}$个单向航行请求。第${i}$个航行请求是从农场${a_i}$到农场 ${b_i，}$航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

请计算可行航行请求的数量，及完成所有可行请求的总费用。

输入格式

第一行:四个整数:${N}$、${M}$、${K}$和${Q}$。

第${2 . .1+M:}$行${i+1}$包含${u_i}$、${v_i}$和${d_i，}$表示第${i}$次飞行。

第${2 + M}$行. .${1+M+Q，}$行${1+M+i}$用${a_i}$和${b_i}$描述第${i}$段

输出格式

第${1}$行:可以使用有效路由的旅行${(}$从${Q}$中${)}$的次数。

第${2}$行:可能使用有效路线的所有行程的最猩能路线费用的总和。

样例

输入样例

3 3 1 3 
3 1 10 
1 3 10 
1 2 7 
3 2 
2 3 
1 2

输出样例

2
24