← 返回题目列表

AtCoder · icpc2015summer_day3_i

I. 诺梅尔冰冷的道路

中文机器翻译题面 查看原题

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

Icy Roads Of Nomel - 原题 PDF
赛事原始英文题册页面
可复制的 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