题目描述

考虑一个无限大的棋盘，以及一个特殊的骑士，其移动类型可以通过获得能力增强道具来改变。骑士的目标是到达格子 $(0, 0)$。

无限大棋盘上的某些格子中放有塔罗牌。如果骑士落在某个有塔罗牌的格子 $(r, c)$ 上，那么他可以选择在该位置购买这张塔罗牌。每张塔罗牌都有价格，并写有两个整数值。写有数值 $a$ 和 $b$ 的塔罗牌允许骑士进行以下相对跳跃：

$$(-a, -b)\quad (a, -b)\quad (-a, b)\quad (a, b)\quad (b, a)\quad (-b, a)\quad (b, -a)\quad (-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$。

2
3 3 2 2 100
1 1 1 1 500

600

2
2 0 2 1 100
6 0 8 1 1

100

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

-1

提示

翻译由 DeepSeek V3.2 完成