题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

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

样例

输入样例

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

输出样例

2
24