Maximizing Array Sum with Alternating Updates

Oleg and Dasha have an array a of length n initialized with all zeros. They are given m integers \(x_1, x_2, \ldots, x_m\). For each \(i\) from 1 to \(m\), they choose an index \(j_i\) (with 1 \(\le\) \(j_i\) \(\le\) \(n\)) and perform the update:

\(a_{j_i} = x_i - a_{j_i}\)

This operation essentially replaces the current value at the chosen index with the difference between \(x_i\) and that value. The operations are performed one after the other in the given order. Your task is to help Oleg and Dasha determine the maximum possible sum of the elements of array a after all the operations, assuming the indices are chosen optimally.

Note: Be careful – if an index is updated more than once, the final value becomes an alternating sum of the corresponding \(x\) values.

inputFormat

The first line contains two integers \(n\) and \(m\) (1 \(\le\) \(n\) \(\le\) \(m\); the limits will be such that a greedy or heap based solution works).

The second line contains \(m\) integers: \(x_1, x_2, \ldots, x_m\), separated by spaces.

outputFormat

Output a single integer – the maximum possible sum of the elements of array \(a\) after performing all \(m\) operations optimally.

sample

1 3
3 1 2

4