{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDo you think that driving is easy? This is not the case when the roads are covered with ice.\u003c/p\u003e\n\n\u003cp\u003eThe city of Nomel has exactly \u003cstrong\u003eN\u003c/strong\u003e+\u003cstrong\u003e1\u003c/strong\u003e streets (west-east roads) and \u003cstrong\u003eM\u003c/strong\u003e+\u003cstrong\u003e1\u003c/strong\u003e avenues (north-south roads). Each street intersects each avenue, so each street is divided into \u003cstrong\u003eM\u003c/strong\u003e blocks and each avenue is divided into \u003cstrong\u003eN\u003c/strong\u003e blocks.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s winter, and each road of the city is covered with a thick ice layer. As driving on ice is a bit tricky, each road has its own time of driving through one block of this road. This value is constant along all blocks of the road.\u003c/p\u003e\n\n\u003cp\u003eObviously, you can drive only through the roads. Now your task is to find a route from the north-western intersection of the city to the south-eastern one with the minimum driving time. This route must also be the shortest one, that is, it should pass through exactly \u003cstrong\u003eN\u003c/strong\u003e+\u003cstrong\u003eM\u003c/strong\u003e blocks.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers \u003cstrong\u003eN\u003c/strong\u003e and \u003cstrong\u003eM\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e, \u003cstrong\u003eM\u003c/strong\u003e ≤ \u003cstrong\u003e500 000\u003c/strong\u003e). The second line contains \u003cstrong\u003eN\u003c/strong\u003e+\u003cstrong\u003e1\u003c/strong\u003e positive integers representing the driving times of Nomel streets, given in the order from north to south. The third line contains \u003cstrong\u003eM\u003c/strong\u003e+\u003cstrong\u003e1 \u003c/strong\u003epositive integers representing the driving times of Nomel avenues, given in the order from west to east. It\u0027s guaranteed that none of these numbers exceed \u003cstrong\u003e10^9\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003ePrint one integer - the required minimum total driving time.\u003c/p\u003e\n\n"}},{"title":"Example","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 3\n5 3 7\n7 2 5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e19\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}