405043: GYM101754 B Big Data

You are given an array a of length n, and an array b of length m. All elements of both arrays are digits from 0 to 9. Using these arrays, construct a table c of size n × m, where the element in the i-th row and the j-th column is determined by c_i, j = a_i·10⁹ + b_j.

Consider all paths from the cell c_1, 1 to the cell c_n, m that consist exclusively of moving down and to the right (that is, from the cell c_i, j you can only move to cells c_{i + 1, j} and c_{i, j + 1}, provided that these cells are inside the table boundaries). Out of all these paths, find one with the largest possible sum of numbers in the visited cells, and print this sum.

The first line contains two integers n and m — sizes of arrays a and b respectively (1 ≤ n, m ≤ 100 000).

The second line contains n integers a₁, ..., a_n (0 ≤ a_i ≤ 9).

The third line contains m integers b₁, ..., b_m (0 ≤ b_j ≤ 9).

Print one integer — the largest sum in visited cells among all paths satisfying rules above in the table c.

3 4
1 1 1
1 1 1 1

6000000006

5 3
1 2 3 4 5
6 7 8

25000000045

7 4
0 7 1 7 6 7 6
4 1 9 7

55000000068

In the second sample, the optimal path first goes down from cell (1, 1) to cell (5, 1), then goes to the right till the end at the cell (5, 3).

In the third sample the optimum path is:

.