Stick Divisions Solution | CSES Problem Set

 

CSES Problem Set

Stick Divisions Solution

You have a stick of length x$x$ and you want to divide it into n$n$ sticks, with given lengths, whose total length is x$x$.

On each move you can take any stick and divide it into two sticks. The cost of such an operation is the length of the original stick.

What is the minimum cost needed to create the sticks?

Input

The first input line has two integers x$x$ and n$n$: the length of the stick and the number of sticks in the division.

The second line has n$n$ integers d1,d2,…,dn$d_1,d_2,\dots ,d_n$: the length of each stick in the division.

Output

Print one integer: the minimum cost of the division.

Constraints

• 1≤x≤109$1\le x\le {10}^9$
  
• 1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$
  
• ∑di=x$\sum d_i=x$
  

Example

Input:
8 3
2 3 3

Output:
13

Explanation: You first divide the stick of length 8$8$ into sticks of length 3$3$ and 5$5$ (cost 8$8$). After this, you divide the stick of length 5$5$ into sticks of length 2$2$ and 3$3$ (cost 5$5$). The total cost is 8+5=13$8+5=13$.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void solve() {

int x,n;

cin>>x>>n;

priority_queue<int,vector<int>,greater<int>>pq;

for (int i = 0; i < n; i++)

{

    int y;cin>>y;

    pq.push(y);

}

int ans=0;

while(pq.size()>1){

    int a=pq.top();

    pq.pop();

    int b=pq.top();

    pq.pop();

    ans+=a+b;

    pq.push(a+b);

}

cout<<ans<<endl;

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

//   cin >> t; 

  while (t--) solve();

  return 0;

}