Background

JOISC2022 D1T2

Problem Description

Kyoto is a world-famous sightseeing city, and it is also known as a grid city. You come to Kyoto for sightseeing, and you plan to visit a famous attraction on foot. In this problem, we consider the following simplified setting.

In the city, there are $H$ east-west streets and $W$ north-south streets, so the city forms an $(H-1)\times(W-1)$ grid. The intersection of the $i$-th street from the north and the $j$-th street from the west is called intersection $(i,j)$.

Different streets may have different materials, widths, and crowd levels, so your walking speed may differ. For each street, your walking time is as follows:

• If you walk one unit length along the $i$-th street from the north, it takes $A_i$ seconds. That is, walking from intersection $(i,c)~\left(i\in[1,H],c\in[1,W)\right)$ to intersection $(i,c+1)$ takes $A_i$ seconds.

• If you walk one unit length along the $j$-th street from the west, it takes $B_j$ seconds. That is, walking from intersection $(c,j)~\left(c\in[1,H),j\in[1,W]\right)$ to intersection $(c+1,j)$ takes $B_j$ seconds.

You are currently at intersection $(1,1)$ and want to go to $(H,W)$. You must walk along the streets, and you do not want to take detours, meaning you will not move north or west.

You want to arrive as early as possible. Please compute the minimum time needed to travel from intersection $(1,1)$ to intersection $(H,W)$ under the given conditions.

Input Format

The first line contains two integers $H,W$, representing the numbers of streets.

The second line contains $H$ integers, where the $i$-th integer $A_i$ represents the walking time on the $i$-th east-west street from the north.

The third line contains $W$ integers, where the $i$-th integer $B_i$ represents the walking time on the $i$-th north-south street from the west.

Output Format

Output one integer in one line, representing the minimum walking time required.

2 2
1 3
2 5

5

5 5
7 1 5 2 8
7 2 4 1 6

20

4 6
454863204 543362989 866044086 813602010
71574269 17945210 688720933 392135202 38174709 168241720

2737473954

Hint

Sample Explanation #1

There are two routes from $(1,1)$ to $(2,2)$:

1. $(1,1)\rightarrow(1,2)\rightarrow(2,2)$, which takes $1+5=6$ seconds.
2. $(1,1)\rightarrow(2,1)\rightarrow(2,2)$, which takes $2+3=5$ seconds.

Therefore, the minimum time is $5$ seconds.

This sample satisfies the constraints of all subtasks.

Sample Explanation #2

The optimal route is shown in the figure below:

This sample satisfies the constraints of all subtasks.

Sample Explanation #3

This sample satisfies the constraints of subtasks $1,3$.

Constraints

For all testdata:

• $2\leq H,W\leq 100000$.
• $1\leq A_i\leq 10^9$ $(i\in[1,H])$.
• $1\leq B_i\leq 10^9$ $(i\in[1,W])$.

The additional constraints and scores for subtasks are as follows:

Translated by ChatGPT 5