Moving 5

Jungyu is trapped in an N×M maze. The maze is divided into 1×1 rooms, and each room contains some candy. The number of candies in room (i, j) is $A_i \times 10^9 + B_j$. The top-left room of the maze is (1, 1), and the bottom-right room is (N, M).

Jungyu is currently at (1, 1) and wants to move to (N, M). When Jungyu is at (r, c), he can move to (r+1, c) or (r, c+1), and each time he visits a room, he can take all the candies in it. He cannot leave the maze.

Find the maximum number of candies Jungyu can take when he moves from (1, 1) to (N, M).

The first line gives the maze dimensions N and M. (1 ≤ N, M ≤ 100,000)

The second line gives $A_1, A_2, \dots, A_N$, and the third line gives $B_1, B_2, \dots, B_M$. (0 ≤ $A_i, B_j$ ≤ 9)

Print the maximum number of candies Jungyu can take when moving to (N, M) on the first line.

The maze from the sample looks as follows, and for convenience the number of candies in (i, j) is written as $A_i, B_j$.