考虑一个无限大的棋盘，上面有一只特殊的骑士，其移动方式会随着获得的道具而改变。骑士的目标是到达坐标 $(0, 0)$。

无限棋盘上的某些方格放置有塔罗牌。如果骑士到达了棋盘上某个有塔罗牌的位置 $(r, c)$，他可以选择购买该位置的卡片。每张塔罗牌都有一个价格，并且上面写有两个整数值。写有值 $a$ 和 $b$ 的塔罗牌允许骑士进行以下相对跳跃：

$$ (−a, −b), (a, −b), (−a, b), (a, b), (b, a), (−b, a), (b, −a), (−b, −a) $$

骑士会保留他购买的所有卡片，并且可以随时使用他拥有的任何卡片进行相对移动。骑士只需在获取卡片时付费，进行跳跃无需额外费用。例如，如果他购买了一张值为 $3$ 和 $2$ 的卡片，以及另一张值为 $8$ 和 $4$ 的卡片，他可以跳跃 $(−2, 3)$，从那里跳跃 $(8, 4)$，稍后再跳跃 $(−3, 2)$。当然，他只有在到达写有 $a$ 和 $b$ 的塔罗牌所在的方格并购买该卡片后，才能进行 $(a, b)$ 的跳跃。

给定棋盘上塔罗牌的位置及其价格，求骑士到达 $(0, 0)$ 所需支付的最小金额。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 1,000$)，表示棋盘上塔罗牌的数量。

接下来的 $n$ 行，每行包含五个空格分隔的整数，描述一张塔罗牌： $$ r\;c\;a\;b\;p $$ ($−10^9 \leq r, c \leq 10^9, 1 \leq a, b, p \leq 10^9$)，其中 $(r, c)$ 是塔罗牌的位置，$a$ 和 $b$ 是偏移量，$p$ 是卡片的价格。

第一张塔罗牌是骑士的初始位置。同一位置可能存在多张塔罗牌。骑士必须拥有至少一张塔罗牌才能移动。

输出一个整数，表示骑士到达目标 $(0, 0)$ 的最小花费。如果无法到达目标，则输出 $-1$。

样例

输入格式 1

2
3 3 2 2 100
1 1 1 1 500

输出格式 1

600

输入格式 2

2
2 0 2 1 100
6 0 8 1 1

输出格式 2

100

输入格式 3

3
1 0 100 50 100
1 50 50 25 100
26 0 20 30 123

输出格式 3

-1