타로 카드 나이트

시간 제한10초메모리 제한512 MB

요약

나이트가 (0, 0)에 도달하기 위해 사야 하는 타로 카드 가격의 최소 합을 구합니다.

난이도: 어려움10점 중 8점
유형: 그래프, 최단 경로, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

무한한 체스판 위에서 특수한 나이트를 생각해 보자. 이 나이트의 이동 방식은 파워업에 따라 바뀔 수 있다. 나이트는 $(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 \le n \le 1,000$ )이 적힌 줄로 시작한다.

이어지는 $n$ 개의 줄에는 공백으로 구분된 정수 다섯 개로 타로 카드가 하나씩 주어진다:

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

여기서 $-10^9 \le r, c \le 10^9$ 이고 $1 \le a, b, p \le 10^9$ 이다. $(r, c)$ 는 카드의 위치, $a$ 와 $b$ 는 오프셋 값, $p$ 는 가격이다. 첫 번째 타로 카드가 나이트의 초기 위치이다. 같은 위치에 타로 카드가 여러 장 있을 수 있다. 나이트가 움직이려면 타로 카드를 가지고 있어야 한다.

출력

나이트가 $(0, 0)$ 에 도달하는 데 드는 최소 비용을 정수 하나로 출력한다. 목표에 도달할 수 없으면 $-1$ 을 출력한다.

예제3

예제 1
입력
```
2
3 3 2 2 100
1 1 1 1 500
```
예상 출력
```
600
```
예제 2
입력
```
2
2 0 2 1 100
6 0 8 1 1
```
예상 출력
```
100
```

예제 3

입력

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

예상 출력

-1