A21303.假期计划

有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，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

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

• 第 1 行：四个整数：N、M、K 和 Q。

• 2..1+M 线：i+1 线包含航班 i 的 u_i、v_i 和 d_i。

• 第 2+M.. 行1+M+Q：第 1+M+i 行以a_i和b_i来描述第 i 次行程

• 第 1 行：可能有有效路线的行程数（Q 以外）。

• 线路 2：所有可能有效路线的行程中，最低可能路线成本的总和。

有三个农场（编号为1..3）;服务器场 1 是一个中心。从农场 3 到农场 1 的航班费用为 10 美元，依此类推。我们希望寻找从农场 3 到农场 2、2->3 和 1->2 的行程。

从 3 到 >2 的旅行只有一条可能的路线，费用为 10+7。从 2 号到 >3 号的行程没有有效的路线，因为没有航班离开农场 2。从 1 到 >2 的行程再次只有一条有效路线，费用为 7。