{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eVasya is currently at a car rental service, and he wants to reach cinema. The film he has bought a ticket for starts in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e minutes. There is a straight road of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e from the service to the cinema. Let\u0027s introduce a coordinate system so that the car rental service is at the point \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e, and the cinema is at the point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThere are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e gas stations along the road, and at each of them you can fill a car with any amount of fuel for free! Consider that this operation doesn\u0027t take any time, i.e. is carried out instantly.\u003c/p\u003e\u003cp\u003eThere are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e cars in the rental service, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them is characterized with two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\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\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u0026nbsp;— the price of this car rent and the capacity of its fuel tank in liters. It\u0027s not allowed to fuel a car with more fuel than its tank capacity \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. All cars are completely fueled at the car rental service.\u003c/p\u003e\u003cp\u003eEach of the cars can be driven in one of two speed modes: normal or accelerated. In the normal mode a car covers \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e kilometer in \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e minutes, and consumes \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e liter of fuel. In the accelerated mode a car covers \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e kilometer in \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e minutes, but consumes \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e liters of fuel. The driving mode can be changed at any moment and any number of times.\u003c/p\u003e\u003cp\u003eYour task is to choose a car with minimum price such that Vasya can reach the cinema before the show starts, i.e. not later than in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e minutes. Assume that all cars are completely fueled initially.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains four positive integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003es\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of cars at the car rental service, the number of gas stations along the road, the length of the road and the time in which the film starts. \u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains two positive integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\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\u003ev\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\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\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)\u0026nbsp;— the price of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th car and its fuel tank capacity.\u003c/p\u003e\u003cp\u003eThe next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003edistinct\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eg\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eg\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eg\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eg\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003es\u003c/i\u003e - 1\u003c/span\u003e)\u0026nbsp;— the positions of the gas stations on the road in arbitrary order.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint the minimum rent price of an appropriate car, i.e. such car that Vasya will be able to reach the cinema before the film starts (not later than in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e minutes). If there is no appropriate car, print \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e.\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\u003e3 1 8 10\n10 8\n5 7\n11 9\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\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\u003e2 2 10 18\n10 4\n20 6\n5 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e20\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample, Vasya can reach the cinema in time using the first or the third cars, but it would be cheaper to choose the first one. Its price is equal to \u003cspan class\u003d\"tex-span\"\u003e10\u003c/span\u003e, and the capacity of its fuel tank is \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e. Then Vasya can drive to the first gas station in the accelerated mode in \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e minutes, spending \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e liters of fuel. After that he can full the tank and cover \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e kilometers in the normal mode in \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e minutes, spending \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e liters of fuel. Finally, he drives in the accelerated mode covering the remaining \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e kilometers in \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e minutes and spending \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e liters of fuel. \u003c/p\u003e"}}]}