Maximizing Yazid's Snack Happiness

Yazid, a student from Tsinghua University, loves snacks. He has n packets of chips (each with a different flavor, numbered 1 through n) and m packets of dried fruits (numbered 1 through m). Note that two packets are of the same type if and only if they are both chips or both dried fruits.

Yazid plans to eat all the snacks in some order. Once he starts eating a packet, he must finish it before moving on. Hence, his eating order can be viewed as a permutation of all snacks.

Each snack has an associated magic value. For chips, the i-th packet has a magic value \(a_i\) (\(1 \le i \le n\)); for dried fruits, the j-th packet has a magic value \(b_j\) (\(1 \le j \le m\)). All magic values are integers and may be negative.

When eating a snack, if the immediately previous snack is of the same type, Yazid increases his happiness by the current snack's magic value. (For the very first snack eaten, no happiness is obtained.) Yazid starts with a happiness of 0. He wants to plan the order in which he eats the snacks so that his total happiness is maximized (note that the final happiness can be negative).

Help Yazid compute the maximum total happiness he can achieve.

Hint: Since the snacks can be rearranged arbitrarily, you can independently choose an optimal ordering for chips and dried fruits. In any contiguous block (or "chain") of the same type, only the first snack does not contribute to happiness, while every subsequent snack contributes its magic value. Thus, for a given set of snacks, if you partition the set into several blocks, the total gained happiness in that type is equal to the sum of all magic values minus the sum of the first element of each block. Since every snack must be eaten, the strategy is to partition the snacks to minimize the sum of the chosen first elements. Equivalently, let \(S\) be the sum of all magic values for that type and let \(F\) be the sum of the first elements in the blocks. The total happiness is \(S-F\). One extreme is to eat all snacks consecutively (one block), in which case the loss is \(\min\{\text{all values}\}\). The other extreme is to eat them all separately, gaining 0. The optimal strategy is to choose a partition that minimizes \(F\), which is equivalent to choosing some of the smallest values as block starters. Perform this optimization for both snack types, and add the results together. (If the optimal arrangement produces a negative value for one type, it is better to take that type in separated blocks, yielding 0 contribution.)

inputFormat

The first line contains two non‐negative integers \(n\) and \(m\) representing the number of chips and dried fruits, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the magic values of the chips. If \(n = 0\), this line is omitted.

The third line contains \(m\) integers \(b_1, b_2, \dots, b_m\) representing the magic values of the dried fruits. If \(m = 0\), this line is omitted.

\(\)Note that the magic values may be negative.

outputFormat

Output a single integer: the maximum total happiness Yazid can achieve.

sample

2 2
5 4
3 6

11