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

题目描述

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

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

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

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

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

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

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

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

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

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$ 表示起点房间的编号和终点房间的编号

输出格式

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

数据范围

对于所有数据保证：$1 \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

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

样例解释1

其中一种方案是：

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

一共花费时间为 $8$

样例输入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

样例解释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$

样例输入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