Innovative Consumer Products Company (ICPC) 计划启动一个绝密项目。该项目包含 $s$ 个子项目。将有 $b \ge s$ 个 ICPC 分部参与此项目，ICPC 希望将每个分部指派给其中一个子项目。换句话说，这些分部将组成 $s$ 个不相交的组，每组负责一个子项目。

在每个月末，每个分部都会向其所在组内的每一个其他分部发送一条消息（发送给每个分部的消息内容不同）。ICPC 有一套特殊的通信协议。每个分部 $i$ 都有一个只有该分部和 ICPC 总部知道的密钥 $k_i$。假设分部 $i$ 想要向分部 $j$ 发送消息。分部 $i$ 使用其密钥 $k_i$ 对消息进行加密。一名受信任的快递员从该分部取走消息并将其送到 ICPC 总部。总部使用密钥 $k_i$ 解密消息，并使用密钥 $k_j$ 重新加密。随后，快递员将这条新加密的消息送到分部 $j$，分部 $j$ 使用其自己的密钥 $k_j$ 进行解密。出于安全原因，快递员一次只能携带一条消息。

给定一个道路网络以及网络中各分部和总部的位置，你的任务是确定在所有可能的分部指派方案中，快递员为传递所有月末消息所需行驶的总距离的最小值。

输入格式

输入的第一行包含四个整数 $n, b, s$ 和 $r$，其中 $n$ ($2 \le n \le 5\,000$) 是交叉路口的数量，$b$ ($1 \le b \le n - 1$) 是分部的数量，$s$ ($1 \le s \le b$) 是子项目的数量，$r$ ($1 \le r \le 50\,000$) 是道路的数量。交叉路口编号为 $1$ 到 $n$。分部位于交叉路口 $1$ 到 $b$，总部位于交叉路口 $b + 1$。接下来的 $r$ 行，每行包含三个整数 $u, v$ 和 $\ell$，表示一条从交叉路口 $u$ 到另一个交叉路口 $v$ ($1 \le u, v \le n$) 的单向道路，长度为 $\ell$ ($0 \le \ell \le 10\,000$)。没有有序对 $(u, v)$ 会出现超过一次，且从任何交叉路口出发都可以到达其他所有交叉路口。

输出格式

显示快递员需要行驶的最小总距离。

样例

样例输入 1

5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

样例输出 1

13

样例输入 2

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

样例输出 2

24