Byteland 覆盖着发达的收费双向高速公路网。每条高速公路连接两个城市。通行费每天都在变化。通行费取决于所走的高速公路及其方向。沿高速公路行驶的费用呈线性变化。换句话说，对于每条高速公路和每个方向，都存在一个常数 $p$，使得每天行驶该方向的通行费变化 $p$（常数 $p$ 可以为负，这意味着通行费减少；$p$ 可以等于 0，即通行费不变；$p$ 也可以大于零，即通行费增加）。所有通行费的变动均在午夜发生。
ByteGuy 住在城市 $a$。他希望拜访住在城市 $b$ 的朋友。ByteGuy 需要在同一天内从 $a$ 开车到 $b$ 并返回 $a$。他是一个节俭的人，所以他想在高速公路通行费尽可能低的时候进行这次旅行。ByteGuy 必须在第 $d$ 天或之前拜访他的朋友。
Byteland 的高速公路网络非常发达，可以在任意两个城市之间通行。每对城市之间最多只有一条直接连接。Byteland 是一个小国。因此，如果 ByteGuy 使用最便宜的路线，他将能够在一天内往返于城市 $b$。保证在最初的 $d$ 天内，每条高速公路的通行费均为正数。
任务
编写一个程序，完成以下操作：
- 读取高速公路的描述、ByteGuy 的居住城市 ($a$) 和他朋友的居住城市 ($b$)，以及天数 $d$；
- 找出在最初 $d$ 天中的某一天，从 $a$ 到 $b$ 再返回的最低旅行成本；
- 将结果写入标准输出。
输入格式
标准输入的第一行包含五个整数 $n, m, a, b, d$，其中 $2 \le n \le 100\,000$，$1 \le m \le 100\,000$，$2 \le d \le 10\,000$。$n$ 是城市数量，$m$ 是高速公路数量，$a$ 是 ByteGuy 的居住城市编号，$b$ 是 ByteGuy 朋友的居住城市编号，$d$ 是 ByteGuy 必须完成旅行的天数。城市编号从 1 到 $n$。你可以假设 ByteGuy 和他的朋友住在不同的城市。接下来的 $m$ 行包含高速公路的描述。每行包含六个整数：$n_1, n_2, c_1, p_1, c_2, p_2$。$n_1$ 和 $n_2$ 是该高速公路连接的城市编号。$c_1$ 和 $c_2$ 分别表示第一天从 $n_1$ 到 $n_2$ 以及从 $n_2$ 到 $n_1$ 的通行费。在接下来的每一天，第一个通行费变化 $p_1$，第二个通行费变化 $p_2$。已知在考虑的天数内（第 1 天到第 $d$ 天），每个通行费都将为正数且不超过 10 000。
输出格式
标准输出的第一行且仅包含一个整数，即在最初 $d$ 天中的某一天，从 $a$ 到 $b$ 再返回的最低旅行成本。
样例
输入 1
4 4 1 4 3 1 2 5 -1 10 -1 3 2 12 2 7 2 3 4 8 -1 20 -3 1 4 27 -2 3 0
输出 1
23
为了区分不同方向的旅行成本，上图中的每条高速公路都由一对边表示。每条边旁边的数字对表示第一天的通行费以及每天的通行费变化量。
在第二天采取路线 1 → 2 → 3 → 4 → 1 的成本为 23。