{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMotorist Kojiro spent \u003cspan class\u003d\"tex-span\"\u003e10\u003c/span\u003e years saving up for his favorite car brand, Furrari. Finally Kojiro\u0027s dream came true! Kojiro now wants to get to his girlfriend Johanna to show off his car to her.\u003c/p\u003e\u003cp\u003eKojiro wants to get to his girlfriend, so he will go to her along a coordinate line. For simplicity, we can assume that Kojiro is at the point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e of a coordinate line, and Johanna is at point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003c/span\u003e. Some points of the coordinate line have gas stations. Every gas station fills with only one type of fuel: \u003cspan class\u003d\"tex-font-style-it\"\u003eRegular-92\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-it\"\u003ePremium-95\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-it\"\u003eSuper-98\u003c/span\u003e. Thus, each gas station is characterized by a pair of integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e — the number of the gas type and its position.\u003c/p\u003e\u003cp\u003eOne liter of fuel is enough to drive for exactly \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e km (this value does not depend on the type of fuel). Fuels of three types differ only in quality, according to the research, that affects the lifetime of the vehicle motor. A Furrari tank holds exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e liters of fuel (regardless of the type of fuel). At the moment of departure from point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e Kojiro\u0027s tank is completely filled with fuel \u003cspan class\u003d\"tex-font-style-it\"\u003eSuper-98\u003c/span\u003e. At each gas station Kojiro can fill the tank with any amount of fuel, but of course, at no point in time, the amount of fuel in the tank can be more than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e liters. Note that the tank \u003cspan class\u003d\"tex-font-style-bf\"\u003ecan\u003c/span\u003e simultaneously have different types of fuel. The car can moves both left and right.\u003c/p\u003e\u003cp\u003eTo extend the lifetime of the engine Kojiro seeks primarily to minimize the amount of fuel of type \u003cspan class\u003d\"tex-font-style-it\"\u003eRegular-92\u003c/span\u003e. If there are several strategies to go from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003c/span\u003e, using the minimum amount of fuel of type \u003cspan class\u003d\"tex-font-style-it\"\u003eRegular-92\u003c/span\u003e, it is necessary to travel so as to minimize the amount of used fuel of type \u003cspan class\u003d\"tex-font-style-it\"\u003ePremium-95\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eWrite a program that can for the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e possible positions of the start \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e minimize firstly, the amount of used fuel of type \u003cspan class\u003d\"tex-font-style-it\"\u003eRegular-92\u003c/span\u003e and secondly, the amount of used fuel of type \u003cspan class\u003d\"tex-font-style-it\"\u003ePremium-95\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains four positive integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e, \u003ci\u003es\u003c/i\u003e, \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ee\u003c/i\u003e, \u003ci\u003es\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — the coordinate of the point where Johanna is, the capacity of a Furrari tank, the number of gas stations and the number of starting points. \u003c/p\u003e\u003cp\u003eNext \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contain two integers each \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 3, - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), representing the type of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th gas station (\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e represents \u003cspan class\u003d\"tex-font-style-it\"\u003eRegular-92\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e — \u003cspan class\u003d\"tex-font-style-it\"\u003ePremium-95\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e — \u003cspan class\u003d\"tex-font-style-it\"\u003eSuper-98\u003c/span\u003e) and the position on a coordinate line of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th gas station. Gas stations don\u0027t necessarily follow in order from left to right.\u003c/p\u003e\u003cp\u003eThe last line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e ≤ \u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003ee\u003c/i\u003e\u003c/span\u003e). Start positions don\u0027t necessarily follow in order from left to right.\u003c/p\u003e\u003cp\u003eNo point of the coordinate line contains more than one gas station. It is possible that some of points \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e or point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003c/span\u003e coincide with a gas station.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them should contain two integers — the minimum amount of gas of type \u003cspan class\u003d\"tex-font-style-it\"\u003eRegular-92\u003c/span\u003e and type \u003cspan class\u003d\"tex-font-style-it\"\u003ePremium-95\u003c/span\u003e, if Kojiro starts at point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. First you need to minimize the first value. If there are multiple ways to do it, you need to also minimize the second value.\u003c/p\u003e\u003cp\u003eIf there is no way to get to Johanna from point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line should look like that \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1 -1\u003c/span\u003e\" (two numbers minus one without the quotes).\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e8 4 1 1\n2 4\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e9 3 2 3\n2 3\n1 6\n-1 0 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 -1\n3 3\n3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e20 9 2 4\n1 5\n2 10\n-1 0 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 -1\n-1 -1\n-1 -1\n-1 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}