{"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 \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/f68e1df4ad172433b9a6bff1157f8c6e?v\u003d1715758236\" alt\u003d\"/problems/travelingmerchant/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eThere is a long east-west road which has \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e towns situated along it, numbered\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e from west to east. All towns buy\n and sell the same kind of goodie. The value of a goodie\n fluctuates according to a weekly schedule. A town buys and\n sells a goodie at its value in that town on that particular\n day. At town \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e, the\n value of a goodie changes by \u003cspan class\u003d\"tex2jax_process\"\u003e$d_\n i$\u003c/span\u003e every day in the first half of a week, and changes by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$-d_ i$\u003c/span\u003e every day in the\n second half of a week. In other words, the value of a goodie at\n town \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e is \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ i$\u003c/span\u003e on Mondays and Sundays,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ i + d_ i$\u003c/span\u003e on Tuesdays\n and Saturdays, \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ i + 2d_\n i$\u003c/span\u003e on Wednesdays and Fridays, and \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ i + 3d_ i$\u003c/span\u003e on Thursdays.\u003c/p\u003e\n \u003cp\u003eA merchant is making a business travel plan. His trip begins\n at a starting town \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e and\n ends at a destination town \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e, visiting each town from\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e (inclusive) exactly once. The\n merchant starts the trip on a Monday. It takes him exactly one\n day to travel between adjacent towns and every day he travels\n to the next town on the path to the destination. He may buy\n exactly one goodie at a town along the trip and sell that\n goodie at a town he visits later. He can only buy once and sell\n once. The merchant would like to know the maximum possible\n profit of \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e travel plans\n with different choices of town \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e and town \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of the input has a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq n \\leq 10^5$\u003c/span\u003e). The next\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines each have two\n integers. The \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth line\n has \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq v_ i \\leq 10^9$\u003c/span\u003e) and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq v_ i + 3 d_ i \\leq 10^9$\u003c/span\u003e). The\n next line has a single integer \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq q \\leq 10^5$\u003c/span\u003e). The following \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e lines each give a pair of integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq s, t \\leq n, s \\neq t$\u003c/span\u003e), representing one travel\n plan from town \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e to town\n \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e. If \u003cspan class\u003d\"tex2jax_process\"\u003e$s \u0026lt; t$\u003c/span\u003e the merchant travels west\n to east, otherwise he travels east to west.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each travel plan, output the maximum profit the merchant\n can make on a single line. If the merchant cannot make any\n profit, output \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\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\u003e5\n1 2\n2 1\n5 0\n4 -1\n7 -2\n5\n1 5\n5 1\n3 1\n4 5\n5 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2\n2\n1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}