Optimal Non-Adjacent Subset Sum After Merging Sequences

You are given two sequences: sequence a of length n and sequence b of length m. You are allowed to insert the elements of sequence b arbitrarily into sequence a at any positions (including at the beginning or the end). Note that the relative order of elements in a must remain unchanged, while the elements of b can be inserted in any order.

After merging the sequences, you need to select a subset of elements from the new sequence with the constraint that no two selected elements are adjacent. Your goal is to maximize the sum of the selected elements. It is allowed to select an empty set.

Important: Because you control the insertion positions as well as the order of b, you can arrange the merged sequence to separate the elements you wish to choose. However, note that the total number of elements in the merged sequence is n + m and thus the maximum number of elements that can be selected (without any two being consecutive) is

$$k\_\max = \left\lfloor\frac{n+m+1}{2}\right\rfloor. $$

To achieve the maximum sum, you should select only the positive numbers. In fact, if there are more than \(k_{\max}\) positive numbers available in total, you can only choose the \(k_{\max}\) largest of them. Otherwise, choose all the positive numbers. Print the maximum achievable sum.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5), representing the lengths of sequences a and b, respectively.

The second line contains n integers representing the elements of sequence a.

The third line contains m integers representing the elements of sequence b.

outputFormat

Output a single integer — the maximum sum you can obtain from a subset of the merged sequence where no two chosen elements are consecutive.

sample

3 2
1 2 3
4 5

12

</p>