在一个城市中有 $n$ 个路口和 $m$ 条有向道路，正在进行一场有趣的赛车比赛。

有趣之处在于：每条道路都是周期性开放和关闭的。每条道路关联两个整数 $(a, b)$，这意味着该道路会开放 $a$ 秒，然后关闭 $b$ 秒，接着再开放 $a$ 秒……所有这些周期都从比赛开始时计时。你必须在道路开放时进入，并在它再次关闭之前离开。

你的目标是从路口 $s$ 出发，并尽可能早地到达路口 $t$。注意，即使所有相邻的道路都处于关闭状态，你也可以在路口等待。

输入格式

最多包含 30 组测试数据。每组数据的第一行包含四个整数 $n, m, s, t$ ($1 \le n \le 300$, $1 \le m \le 50,000$, $1 \le s, t \le n$)。接下来的 $m$ 行，每行包含五个整数 $u, v, a, b, c$ ($1 \le u, v \le n$, $1 \le a, b, c \le 10^5$)，表示有一条从路口 $u$ 到路口 $v$ 的道路。该道路开放 $a$ 秒，然后关闭 $b$ 秒（依此类推）。驾驶车辆通过该道路所需的时间为 $c$。没有道路连接同一个路口，但一对路口之间可能有多条道路连接。

输出格式

对于每组测试数据，输出到达目的地所需的最短时间（以秒为单位）。保证一定能从 $s$ 到达 $t$。

样例

输入格式 1

3 2 1 3
1 2 5 6 3
2 3 7 7 6
3 2 1 3
1 2 5 6 3
2 3 9 5 6

输出格式 1

Case 1: 20
Case 2: 9