{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eConsider an infinite chessboard and a special knight whose\n move types can change given power-ups. The knight is trying to\n reach square \u003cspan class\u003d\"tex2jax_process\"\u003e$(0, 0)$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eSome of the squares of the infinite chessboard have tarot\n cards on them. If the knight lands on some position\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(r, c)$\u003c/span\u003e on the infinite\n chessboard with a tarot card on it, then the knight has the\n option of buying that card at that position. Each tarot card\n will have a price, and will have two integer values written on\n it. The tarot card with values \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e written on it allow the knight to\n make relative jumps:\u003c/p\u003e\n \u003ccenter\u003e\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(-a, -b)\\qquad (a, -b)\\qquad\n (-a, b)\\qquad (a, b)\\qquad (b, a)\\qquad (-b, a)\\qquad (b,\n -a)\\qquad (-b, -a)$\u003c/span\u003e\n \u003c/center\u003e\n \u003cp\u003eThe knight retains all cards he purchases and can make\n relative moves from any of the cards he owns any number of\n times. The knight must only pay when obtaining cards and can\n perform jumps at no additional cost. For example, if he buys a\n card with \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e and another card with\n \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e, he may jump by \u003cspan class\u003d\"tex2jax_process\"\u003e$(-2, 3)$\u003c/span\u003e, and from there jump by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(8, 4)$\u003c/span\u003e, and later jump\n by \u003cspan class\u003d\"tex2jax_process\"\u003e$(-3, 2)$\u003c/span\u003e. Of course,\n he cannot make a jump \u003cspan class\u003d\"tex2jax_process\"\u003e$(a,b)$\u003c/span\u003e until after he arrives at a\n square with a tarot card with \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e on it, and purchases that\n card.\u003c/p\u003e\n \u003cp\u003eGiven positions of the tarot cards on the board and their\n prices, find the least amount that the knight must pay to reach\n square \u003cspan class\u003d\"tex2jax_process\"\u003e$(0, 0)$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eEach test case will begin with a line containing a single\n integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\\! \\le \\! n\\! \\le \\! 1\\, 000$\u003c/span\u003e),\n which is the number of tarot cards on the chessboard.\u003c/p\u003e\n \u003cp\u003eEach of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n lines contains a description of a tarot card in five\n space-separated integers:\u003c/p\u003e\n \u003ccenter\u003e\n \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e\n \u003c/center\u003e\n \u003cp\u003e(\u003cspan class\u003d\"tex2jax_process\"\u003e$-10^9\\! \\le \\! r, c\\! \\le \\!\n 10^9, 1\\! \\le \\! a, b, p\\! \\le \\! 10^9$\u003c/span\u003e), where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(r,c)$\u003c/span\u003e is the location of\n the tarot card, \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e are the offset values,\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e is the price of\n the card.\u003c/p\u003e\n \u003cp\u003eThe first tarot card is the initial position of the knight.\n Multiple tarot cards may exist at the same location. The knight\n must have a tarot card to move.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a single integer, which is the minimum cost for the\n knight to reach the goal at \u003cspan class\u003d\"tex2jax_process\"\u003e$(0,0)$\u003c/span\u003e. Output \u003cspan class\u003d\"tex2jax_process\"\u003e$-1$\u003c/span\u003e if it is not possible to reach\n the goal.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 3 2 2 100\n1 1 1 1 500\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e600\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 0 2 1 100\n6 0 8 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e100\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 0 100 50 100\n1 50 50 25 100\n26 0 20 30 123\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}