Knight of the Tarot Cards

Consider an infinite chessboard and a special knight whose move types can change given powerups. The knight is trying to reach square $(0, 0)$.

Some squares of the infinite chessboard have tarot cards on them. If the knight lands on a position $(r, c)$ with a tarot card on it, the knight can buy that card at that position. Each tarot card has a price and two integer values written on it. The tarot card with values $a$ and $b$ allows the knight to make these relative jumps:

$(-a, -b)$, $(a, -b)$, $(-a, b)$, $(a, b)$, $(b, a)$, $(-b, a)$, $(b, -a)$, $(-b, -a)$

The knight keeps every card it buys and can make relative moves from any card it owns, any number of times. The knight pays only when it obtains a card. Jumps cost nothing. For example, if the knight buys a card with 3 and 2 and another card with 8 and 4, it may jump by $(-2, 3)$, then by $(8, 4)$, and later by $(-3, 2)$. The knight cannot make a jump $(a, b)$ until it arrives at a square with a tarot card showing $a$ and $b$ and buys that card.

Given the positions of the tarot cards and their prices, find the least amount the knight must pay to reach $(0, 0)$.

Each test case begins with a line containing a single integer $n$ ($1 \le n \le 1,000$), the number of tarot cards on the chessboard.

Each of the next $n$ lines describes a tarot card with five space-separated integers:

$r$ $c$ $a$ $b$ $p$

Here $-10^9 \le r, c \le 10^9$ and $1 \le a, b, p \le 10^9$. The pair $(r, c)$ is the location of the card, $a$ and $b$ are its offset values, and $p$ is its price. The first tarot card is the knight's initial position. Multiple tarot cards may exist at the same location. The knight must have a tarot card to move.

Output a single integer, the minimum cost for the knight to reach $(0, 0)$. Output $-1$ if the goal cannot be reached.