该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Sam 最近很喜欢玩《杀戮尖塔》这个经典的卡牌 roguelike 游戏。

Sam 每次来到新关卡的时候，他的角色等级 $level$ 是 $1$ 级。

而在每一关游戏中一共有 $n$ 个房间，其中有一个房间是起点，一个房间是终点，Sam 的任务就是从起点到达终点。

并且这些房间之间存在 $m$ 条单向通道，第 $i$ 条单向通道允许你从一个房间 $a_i$ 走到另一个房间 $b_i$（不允许从 $b_i$ 走到 $a_i$），但是每条通道上都会有一些怪物，为了方便，我们用 $monster_i$ 来表示这个通道的怪物等级，而 Sam 通过这个通道需要花费 $\lceil monster_i/level \rceil$ 的时间。

这个游戏相当简单，所以 Sam 总是能以最快的速度通过每一关。

但是到了后期，Sam 发现游戏的难度加大了！

游戏出现了两种新的元素：

1. 每一关中有 $p$ 个铁匠，第 $i$ 个铁匠会出现在编号为 $pos_i$ 的房间内，在这个 铁匠 处可以花费 $cost_i$ 的时间让自己的角色等级提升 $2$ 倍（允许在同一个房间的 铁匠 处多次提升，且一个房间可以有多个铁匠）
2. 有一些通道内的怪物升级为 诅咒怪物，在 Sam 经过这个通道后，Sam 的等级不论提升到多少级，都会直接变回 $1$ 级。

难度加大以后的游戏对 Sam 来说就有了一些挑战，于是他想知道如果提前知道了整个游戏地图的形态，他最少需要花费多少时间才能通过这一关？

P.S. $\lceil x \rceil$ 表示向上取整，即值为不小于 $x$ 的最小整数。

输入格式

输入第一行包含两个整数 $n,m,p$ 分别表示房间数量，单向通道数量和铁匠数量。

接下来 $m$ 行，每行包含三个整数 $a_i,b_i,monster_i,op_i$ 分别表示一条单向通道的信息，其中 $op_i=0$ 则表示这条单向通道内是普通怪物，$op_i=1$ 则表示这条通道的怪物是 诅咒怪物。

接下来 $p$ 行，每行包含两个整数 $pos_i,cost_i$ 表示第 $i$ 个铁匠的信息。

最后一行包含两个整数 $st,ed$ 表示起点房间的编号和终点房间的编号。

输出格式

输出一个整数表示 Sam 最少需要花费的时间，如果无论如何 Sam 都无法到达，则输出 Impossible!。

输入输出样例 #1

输入 #1

5 5 1
1 2 4 0
2 3 6 1
3 4 8 1
4 5 10 0
1 5 100 0
1 1
1 5

输出 #1

8

输入输出样例 #2

输入 #2

5 4 2
1 2 4 0
2 3 6 1
3 4 8 1
4 5 10 0
1 1
3 1
1 5

输出 #2

19

输入输出样例 #3

输入 #3

5 4 2
1 2 4 0
2 3 6 0
3 4 8 0
4 5 10 0
1 1
3 1
1 5

输出 #3

8

说明/提示

数据范围

对于所有数据保证：$1 \leq p \leq n \leq 20000, 1 \leq m \leq 70000, 1 \leq monster_i, cost_i \leq 1000000, 1 \leq a_i,b_i,pos_i \leq n$。

样例解释1

其中一种方案是：

1. 在房间 $1$ 的铁匠处升级 $7$ 次，等级变为 $1 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128$ 级，花费时间 $7$。
2. 然后通过第 $5$ 条通道花费时间 $\lceil 100/128 \rceil =1$。

一共花费时间为 $8$。

样例解释2

其中一种方案是：

1. 在房间 $1$ 的铁匠处处升级 $3$ 次等级变为 $1 * 2 * 2 * 2 = 8$ 级，花费时间 $3$。
2. 通过第 $1$ 条通道花费时间 $\lceil 4/8 \rceil = 1$。
3. 通过第 $2$ 条通道花费时间 $\lceil 6/8 \rceil = 1$。
4. 在房间 $3$ 的铁匠处升级 $2$ 次，等级变为 $1 * 2 * 2 = 4$ 级，花费时间 $2$。
5. 通过第 $3$ 条通道花费时间为 $\lceil 8/4 \rceil = 2$。
6. 通过第 $4$ 条通道花费时间为 $\lceil 10/1 \rceil = 10$。

一共花费时间为 $19$。