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 ci, j = ai·109 + bj.
Consider all paths from the cell c1, 1 to the cell cn, m that consist exclusively of moving down and to the right (that is, from the cell ci, j you can only move to cells ci + 1, j and ci, 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 a1, ..., an (0 ≤ ai ≤ 9).
The third line contains m integers b1, ..., bm (0 ≤ bj ≤ 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: 
.
