Moving 4

Time limit2sMemory limit512 MB

Summary

Find the minimum total trash on a monotone path from (0, 0) to (N, M), where each right move costs A of its row and each down move costs B of its column.

Level: Medium7 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

Junkyu is trapped in a maze of size $(N+1)\times(M+1)$ . The maze is divided into $1\times1$ rooms. The top-left room is $(0, 0)$ , and the bottom-right room is $(N, M)$ . Junkyu is currently at $(0, 0)$ and wants to reach $(N, M)$ . From $(r, c)$ , Junkyu can move through a door to $(r+1, c)$ or $(r, c+1)$ . Junkyu cannot leave the maze. Trash is now lying in the gaps between the doors. Whenever Junkyu moves from $(r, c)$ to $(r+1, c)$ , Junkyu must take all the trash in that gap, which is $B_c$ pieces. Moving from $(r, c)$ to $(r, c+1)$ requires taking $A_r$ pieces. Find the minimum amount of trash Junkyu must take to reach $(N, M)$ .

Input

The first line contains the maze size $N$ and $M$ ( $1 \le N, M \le 500{,}000$ ). The next line contains $N+1$ integers $A_i$ ( $1 \le A_i \le 10^9$ ). The next line contains $M+1$ integers $B_i$ ( $1 \le B_i \le 10^9$ ).

Output

Print the minimum amount of trash Junkyu must take to reach $(N, M)$ on the first line.

Examples3

Example 1
Input
```
2 3
60 20 90
10 90 80 70
```
Expected output
```
140
```
Example 2
Input
```
1 1
1 1
1 1
```
Expected output
```
2
```

Example 3

Input

2 2
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Expected output

4000000000