AtCoder 原图名称已被搁置;此后,原始图像取自英语原文,现已完整保存。

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem I. Icy Roads Of Nomel
Input le: iron.in
Output le: iron.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Do you think that driving is easy? This is not the case when the roads are covered with ice.
The city of Nomel has exactly N + 1 streets (west-east roads) and M + 1 avenues (north-south
roads). Each street intersects each avenue, so each street is divided into M blocks and each avenue
is divided into N blocks.
It's 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.
Obviously, you can drive only through the roads. Now your task is to nd 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 N + M blocks.
Input
The rst line of the input le contains two integers N and M (1 ≤N, M ≤500 000). The second
line contains N + 1 positive integers representing the driving times of Nomel streets, given in the
order from north to south. The third line contains M +1 positive integers representing the driving
times of Nomel avenues, given in the order from west to east. It's guaranteed that none of these
numbers exceed 109.
Output
Output one integer the required minimum total driving time.
Examples
iron.in iron.out
2 3 19
5 3 7
7 2 5 6
Page 9 of 10