Elemental Burst Optimization

A mage in the world of Teyvat can cast two types of elemental attacks: fire and ice. She has n fire attacks and m ice attacks. The damage of the i-th fire attack is \(a_i\) (for \(i=1,2,\dots,n\)) and that of the j-th ice attack is \(b_j\) (for \(j=1,2,\dots,m\)).

The attacks interact with the enemy according to the following rules:

• If the enemy has no element attached (initial state), any elemental attack will attach its corresponding element to the enemy and deal its base damage.
• If a fire attack is used on an enemy with an ice element attached, the attack deals \(2a_i\) damage (i.e. the base damage is doubled) and then clears the attached element.
• If an ice attack is used on an enemy with a fire element attached, the attack deals \(b_j+k\) damage (i.e. an additional constant bonus \(k\) is added) and then clears the attached element.

The mage can choose the order of her attacks arbitrarily. Note that after each attack the enemy's elemental state is updated according to the rules. When an attack is not used to trigger a reaction (i.e. the enemy is neutral), only the base damage is dealt.

Help the mage maximize the total damage dealt to the enemy.

Observation: If no reaction is triggered, an attack simply deals its base damage. When a reaction is triggered, the paired attacks (one attack that attached an element and then a reactive attack of the opposite element) provide an extra bonus damage: when an ice attack is used on a fire‐attached enemy, the bonus is \(k\), and when a fire attack is used on an ice‐attached enemy, the bonus is \(a_i\) (i.e. the base damage of the fire attack). Note that if \(a_i\le k\), then triggering the reaction with this fire attack yields a bonus no better than using the reaction rule with ice. Therefore, the optimal strategy is to form as many pairs as possible (with at most \(p = \min(n,m)\) pairs) and, for each pair, decide whether to use a fire reaction or an ice reaction to maximize the extra bonus. In particular, if a fire attack has \(a_i > k\), using it as the reactive attack yields an extra bonus of \(a_i\) (instead of \(k\)), and the additional bonus is \(a_i-k\).

The total damage is the sum of the base damage of all spells plus the additional bonus from the pairs. Formally, if \(p=\min(n,m)\) pairs are formed and we choose to use \(x\) optimal fire reactions (with fire attacks having \(a_i > k\)) then the maximum total damage is given by:

[ \text{Total Damage} = \sum_{i=1}^{n} a_i + \sum_{j=1}^{m} b_j + \left(\sum_{\text{selected fire attacks}} a_i + (p - x)\cdot k\right). ]

Your task is to compute this maximum total damage.

inputFormat

The first line of input contains three integers: n, m and k (where n is the number of fire attacks, m is the number of ice attacks, and k is the bonus damage for an ice reaction).

The second line contains n space-separated integers: \(a_1,a_2,\dots,a_n\) representing the damage of each fire attack.

The third line contains m space-separated integers: \(b_1,b_2,\dots,b_m\) representing the damage of each ice attack.

outputFormat

Output a single integer — the maximum total damage the mage can deal by optimally ordering her attacks and triggering as many reactions as possible.

sample

3 2 5
10 2 7
1 2

39