1298 : 逃离迷宫

Reverie被困入了一个迷宫！
这个迷宫总共有$n$个房间，Reverie开始在1号房间，n号房间为迷宫的出口。
每进入一次i号房间都需要缴纳$a_i$的过路费（包括初始的1号房间）。
每个房间有一张纸条和一个箱子。
纸条上写着数字$d_i$，代表Reverie下一个可以到达的房间编号。
Reverie也可以选择花费$b_i$的钱打开箱子，箱子中有一个咒语$c_i$，打开箱子之后Reverie可以移动到i+k号房间。
k满足$k|c_i 且 i+k \leq n$.
求Reverie走出迷宫的最小花费，若无法走出，输出-1。

第一行一个正整数n，代表迷宫共有n个房间。
接下来n行，每行包含四个整数$a_i,b_i,c_i,d_i$,意义如前所述。
Limits:
$2 \leq n \leq 1000$
$1 \leq d_i  \leq n$
$1 \leq a_i,b_i,c_i \leq 2×10^5$

一行一个整数代表走出迷宫的最小花费。

5
1 2 2 4
2 2 2 2
1 1 2 2
100 1 1 1
1 1 1 1

6

Wannacry-03