/*
Problem URL:
https://cses.fi/problemset/task/1161
*/

#include <bits/stdc++.h>

using namespace std;

void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (s != "") {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}

// DEBUG INFO:

// helper for printing a pair
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

// helper for printing a container
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

// SHORTENED MACROS
#define ll long long
#define ull unsigned long long
#define ld long double
#define nl "\n"
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define MOD 1000000007
#define x first
#define y second

// VERY USEFUL ORDERED CONTAINER TO USE INSTEAD OF STL
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x)                                                         \
  tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>

/*

Useful Links:

- the below link matches time complexity with input size
https://codeforces.com/blog/entry/21344

Problems to complete:
- https://cses.fi/problemset/task/1161
- https://codeforces.com/problemset/problem/1472/E
- http://usaco.org/index.php?page=viewproblem2&cpid=225
- https://codeforces.com/contest/860/problem/D
- http://www.usaco.org/index.php?page=viewproblem2&cpid=1233
- http://www.usaco.org/index.php?page=viewproblem2&cpid=645

Brainstorming:

Important Info:
-

Thoughts:
- this problem is definitely greedily oriented:
  - the optimal move is probably to divide in half as much as possible in
    general (i think) because you're still using the most

- sorting stick sizes from greatest to least and initializing two vectors, we
  can add the current element to the vector with a smaller sum
  - from here, we can add the sum of the previous array to the current vector
  - we can continue this until all elements have been split up into their own
    vector
  - this works: just needs optimization
  - is there a way to recursively calculate the subarray's split while
    calculating an array's split?
    - need a recursive solution that optimizes so the total is in O(NlogN) time:
      can also make the equalarr division a O(logN) task (currently O(N))

- need to modify our custom array split function to see whether it works better;
  also, is this not an O(N^2) algorithm? how was it able to run in O(NlogN)
  time?

*/
struct customArr {
  ull sum = 0;
  deque<ull> arr;
};

int sum, N;
ull total = 0;

pair<customArr, customArr> equalSums(customArr x) {
  // assuming that equalSums is already greatest-to-least sorted

  cout << x.arr << " " << x.sum << nl;

  total += x.sum;
  customArr a, b;
  while (!x.arr.empty()) {
    if (a.sum >= b.sum) {
      b.sum += x.arr.front();
      b.arr.push_back(x.arr.front());
      x.arr.pop_front();
    } else {
      a.sum += x.arr.front();
      a.arr.push_back(x.arr.front());
      x.arr.pop_front();
    }
  }

  cout << a.arr << " " << a.sum << nl;
  cout << b.arr << " " << b.sum << nl;

  return make_pair(a, b);
}

int main(void) {

  cin >> sum >> N;

  customArr start;
  for (int i = 0; i < N; i++) {
    start.arr.push_back(0);
    cin >> start.arr[i];
    start.sum += start.arr[i];
  }

  sort(all(start.arr), greater<int>());
  //   cout << start.arr << nl;

  deque<customArr> allElems;
  allElems.push_back(start);
  while (!allElems.empty()) {

    customArr top = allElems.front();
    allElems.pop_front();

    if (sza(top.arr) == 1) {
      continue;
    }

    pair<customArr, customArr> res = equalSums(top);

    // cout << res.first.arr << " " << res.second.arr << " " << total << nl;

    allElems.push_back(res.first);
    allElems.push_back(res.second);
  }

  cout << total << nl;
  return 0;
}