{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eVova bought a new wide-angle lens for his camera a few days ago. Now he wants to take a\r\npanoramic photo with this lens, and that is the reason why he decided to climb the nearest hill.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere is a single narrow serpentine path leading from base of the hill to its top.\r\nVova introduced coordinate axes in such a way that \u003ci\u003eOY\u003c/i\u003e is directed along the hill side from\r\nbase to top and \u003ci\u003eOX\u003c/i\u003e is orthogonal to it. The path is represented as a polyline with \u003ci\u003en\u003c/i\u003e segments,\r\nvertices of which follow in the order of strictly increasing \u003ci\u003ey\u003c/i\u003e-coordinate. For each segment of the path, Vova knows the\r\ntime required to change \u003ci\u003ex\u003c/i\u003e-coordinate by one while moving along this segment.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eMoreover, Vova can use cableways. They start at some point of the path, run strictly up the hill parallel to \u003ci\u003eOY\u003c/i\u003e axis and end at the\r\nnext intersection with the path. Vova knows the time required to use each cableway.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eHelp Vova climb the hill before it gets dark! Note that Vova is so\r\ndetermined that he will refuse to go down the hill even if this action helps him to\r\nclimb the hill faster.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains a number of segments in the path \u003ci\u003en\u003c/i\u003e (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e).\r\nThe next line contains \u003ci\u003en\u003c/i\u003e + 1 integers which are \u003ci\u003ex\u003c/i\u003e-coordinates of polyline vertices in the order from\r\nbase to top. No two consecutive vertices have the same \u003ci\u003ex\u003c/i\u003e-coordinate.\r\nThe \u003ci\u003ei\u003c/i\u003e-th of the following \u003ci\u003en\u003c/i\u003e lines contains integers \u003ci\u003ev\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e and \u003ci\u003em\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e which are time required to change \u003ci\u003ex\u003c/i\u003e-coordinate by one\r\nwhile moving along the \u003ci\u003ei\u003c/i\u003e-th segment and a number of cableways starting at the \u003ci\u003ei\u003c/i\u003e-th segment, respectively. The rest of this line\r\ncontains \u003ci\u003em\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e pairs of integers describing the cableways. Each cableway is described with \u003ci\u003ex\u003c/i\u003e-coordinate of its start point and\r\ntime required to use this cableway. The cableways are described in the order from base to top. No two cableways start\r\nat the same point. If a cableway starts at the common point of two path segments, it encounters in the description of only one segment.\r\nIt is guaranteed that each cableway ends somewhere on the path.\r\nAll numbers in lines are separated by spaces. All coordinates don\u0027t exceed 10\u003csup\u003e6\u003c/sup\u003e in their absolute value.\r\nAll times are positive and don\u0027t exceed 10\u003csup\u003e6\u003c/sup\u003e. The total number of cableways doesn\u0027t exceed 10\u003csup\u003e5\u003c/sup\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the minimal time required to climb the hill.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","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\u003e4\r\n0 5 15 10 0\r\n1 1 1 100\r\n1 1 7 1\r\n1 0\r\n1 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\r\n0 10 0 10\r\n10 0\r\n10 1 10 1\r\n10 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e101\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}