Problem Background

JOISC2022 Day 1 Task 2

Problem Description

Kyoto is a world-class tourist destination and is also known as a grid city. You have come to Kyoto for sightseeing and plan to explore a famous attraction on foot. In this problem, we consider a simplified scenario.

In the city, there are $H$ east-west streets and $W$ north-south streets, forming a grid of size $(H-1) \times (W-1)$. The intersection of the $i$-th street from the north and the $j$-th street from the west is denoted as junction $(i,j)$.

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

• If you walk a unit length on the $i$-th east-west street, it takes $A_i$ seconds. That is, it takes $A_i$ seconds to move from junction $(i,c)$ to junction $(i,c+1)$ for $i \in [1,H]$ and $c \in [1,W)$.

• If you walk a unit length on the $j$-th north-south street, it takes $B_j$ seconds. That is, it takes $B_j$ seconds to move from junction $(c,j)$ to junction $(c+1,j)$ for $c \in [1,H)$ and $j \in [1,W]$.

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

You aim to arrive at your destination as soon as possible. Calculate the minimum time required to travel from junction $(1,1)$ to junction $(H,W)$ under the given conditions.

Input Format

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

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

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

Output Format

Output a single integer, which is the minimum walking time required.

Sample Input and Output

Sample Input #1

2 2
1 3
2 5

Sample Output #1

5

Sample Input #2

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

Sample Output #2

20

Sample Input #3

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

Sample Output #3

2737473954

Notes

[Sample Explanation #1]

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

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

Thus, the minimum time is $5$ seconds.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #2]

The optimal route is shown in the following image:

This sample satisfies the constraints of all subtasks.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks 1 and 3.

[Data Range]

For all data, the following constraints apply:

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

Detailed subtask constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分