Three Bags
Contest: Codeforces Round 695 (Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, greedy

You are given three bags. Each bag contains a non-empty multiset of numbers. You can perform a number of operations on these bags. In one operation, you can choose any two non-empty bags, and choose one number from each of the bags. Let's say that you choose number $$$a$$$ from the first bag and number $$$b$$$ from the second bag. Then, you remove $$$b$$$ from the second bag and replace $$$a$$$ with $$$a-b$$$ in the first bag. Note that if there are multiple occurrences of these numbers, then you shall only remove/replace exactly one occurrence.

You have to perform these operations in such a way that you have exactly one number remaining in exactly one of the bags (the other two bags being empty). It can be shown that you can always apply these operations to receive such a configuration in the end. Among all these configurations, find the one which has the maximum number left in the end.

Input format:
The first line of the input contains three space-separated integers $$$n_1$$$, $$$n_2$$$ and $$$n_3$$$ ($$$1 \le n_1, n_2, n_3 \le 3\cdot10^5$$$, $$$1 \le n_1+n_2+n_3 \le 3\cdot10^5$$$) — the number of numbers in the three bags.

The $$$i$$$-th of the next three lines contain $$$n_i$$$ space-separated integers $$$a_{{i,1}}$$$, $$$a_{{i,2}}$$$, ..., $$$a_{{i,{{n_i}}}}$$$ ($$$1 \le a_{{i,j}} \le 10^9$$$) — the numbers in the $$$i$$$-th bag.

Output format:
Print a single integer — the maximum number which you can achieve in the end.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example input, let us perform the following operations:

$$$[1, 2], [6, 3, 4, 5], [5]$$$

$$$[-5, 2], [3, 4, 5], [5]$$$ (Applying an operation to $$$(1, 6)$$$)

$$$[-10, 2], [3, 4], [5]$$$ (Applying an operation to $$$(-5, 5)$$$)

$$$[2], [3, 4], [15]$$$ (Applying an operation to $$$(5, -10)$$$)

$$$[-1], [4], [15]$$$ (Applying an operation to $$$(2, 3)$$$)

$$$[-5], [], [15]$$$ (Applying an operation to $$$(-1, 4)$$$)

$$$[], [], [20]$$$ (Applying an operation to $$$(15, -5)$$$)

You can verify that you cannot achieve a bigger number. Hence, the answer is $$$20$$$.

Example input:
2 4 1
1 2
6 3 4 5
5

Example output:
20

Example input:
3 2 2
7 5 4
2 9
7 1

Example output:
29

Editorial:
Model the problem as a rooted tree (graph). There are $$$n_1+n_2+n_3$$$ nodes, corresponding to the elements from the three bags. Edges between two nodes represent an operation on the two elements and it can be seen that an edge can exist only between nodes of elements from different sets. A directed edge from $$$b$$$ to $$$a$$$ means that $$$b$$$ is removed and $$$a$$$ is replaced to $$$a-b$$$. All edges are directed towards the root.
In the given rooted tree, operations are applied bottom up, that is, an operation is applied on a leaf node and its parent, and the leaf node is removed. The process is continued until only the root node is remaining.
It is easy to see that the value of the element at the end of all operations is the sum of elements at even depth minus the sum of elements at odd depth (depth is $$$0$$$ indexed).
Claim: The constructed rooted tree is valid, if the elements at odd depth are
1. are from at least two different bags, or
2. contain all elements from one bag.
Proof:
Consider a rooted tree with all elements at odd depth from exactly one bag (say $$$X$$$) which doesn't fulfil criteria $$$2$$$. No remaining elements from bag $$$X$$$ can be connected to the nodes at odd depth, making it impossible to construct a tree. This implies that $$$1$$$ must hold.
However, if criteria $$$2$$$ holds, no elements from bag $$$X$$$ remain to be connected, and thus the tree can be constructed.
Hence proved.
Now, we have to minimise either of the two cases, which is the solution to the problem.
For the first case, we can choose the two smallest numbers such that they both appear in different bags to be at odd depth.
For the second case, we can choose all numbers from the bag where the sum of the numbers is minimum to be at odd depth.