{"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目前正在一家汽车租赁服务中,他想要去电影院。他购买的电影将在\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e分钟后开始。从汽车租赁服务到电影院有一条长度为\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e的笔直道路。让我们引入一个坐标系,使得汽车租赁服务在点\u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e,电影院在点\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e沿途有\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e个加油站,每个加油站都可以免费加满汽车的燃料!请注意,这个操作不需要任何时间,即瞬间完成。\u003c/p\u003e\u003cp\u003e汽车租赁服务中有\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e辆汽车,第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e辆汽车由两个整数\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和\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\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e的燃料。所有汽车在汽车租赁服务中都已经加满了燃料。\u003c/p\u003e\u003cp\u003e每辆汽车可以以两种速度模式之一行驶:普通模式或加速模式。在普通模式下,汽车在\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e分钟内可以行驶\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e公里,消耗\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e升燃料。在加速模式下,汽车在\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e分钟内可以行驶\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e公里,但消耗\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e升燃料。行驶模式可以随时改变,且可以任意次数切换。\u003c/p\u003e\u003cp\u003e你的任务是选择一辆价格最低的汽车,使得Vasya能在电影开始前到达电影院,即不迟于\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e分钟。假设所有汽车在起始时都已经加满了燃料。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含四个正整数\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和\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)—汽车租赁服务中的汽车数量、沿途的加油站数量、道路长度和电影开始的时间。\u003c/p\u003e\u003cp\u003e接下来的\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e行中,每行包含两个正整数\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和\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)—第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e辆汽车的租金和油箱容量。\u003c/p\u003e\u003cp\u003e接下来一行包含\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e个\u003cspan class\u003d\"tex-font-style-bf\"\u003e不同\u003c/span\u003e的整数\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)—道路上加油站的位置,顺序任意。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一辆合适汽车的最低租金价格,即Vasya能在电影开始前到达电影院的汽车。如果没有合适的汽车,输出\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e。\u003c/p\u003e"}},{"title":"示例1","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"}},{"title":"示例2","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"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,Vasya可以选择第一辆或第三辆汽车及时到达电影院,但选择第一辆汽车更便宜。它的价格等于\u003cspan class\u003d\"tex-span\"\u003e10\u003c/span\u003e,油箱容量为\u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e。然后Vasya可以以加速模式在\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e分钟内开到第一个加油站,消耗\u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e升燃料。然后他可以加满油箱,在\u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e分钟内以普通模式行驶\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e公里,消耗\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e升燃料。最后,他以加速模式行驶剩下的\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e公里,在\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e分钟内消耗\u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e升燃料。\u003c/p\u003e"}}]}