import heapq
n,m= map(int,input().split())
a = list(map(int,input().split()))
b = [-i for i in a]
heapq.heapify(a)
heapq.heapify(b)
seats = 0
maxVal = 0
minVal = 0
while seats<n:
minSeat = heapq.heappop(a)
minVal+=minSeat
minSeat-=1
if minSeat>0:
heapq.heappush(a,minSeat)
maxSeat = heapq.heappop(b)
maxVal+=abs(maxSeat)
maxSeat+=1
if maxSeat<0:
heapq.heappush(b,maxSeat)
seats+=1
print(maxVal,minVal)
#include <iostream>
#include<algorithm>
#include<queue>
using namespace std;
int
main ()
{
int passengers, seats;
cin >> passengers >> seats;
priority_queue<int,vector<int>,less<int>> eamptysets;
priority_queue<int,vector<int>,greater<int>> eamptysets_min;
while(seats--)
{
int x;
cin>>x;
eamptysets.push(x);
eamptysets_min.push(x);
}
int max=0,min=0;
int temp;
int passengers2=passengers;
while(passengers--)
{
max+=eamptysets.top();
temp=eamptysets.top();
eamptysets.pop();
if(temp-1!=0)
eamptysets.push(temp-1);
}
int temp_min;
while(passengers2--)
{
min+=eamptysets_min.top();
temp_min=eamptysets_min.top();
eamptysets_min.pop();
if(temp_min-1!=0)
eamptysets_min.push(temp_min-1);
}
cout<<max<<" "<<min;
return 0;
}
1399A - Remove Smallest | 208A - Dubstep |
1581A - CQXYM Count Permutations | 337A - Puzzles |
495A - Digital Counter | 796A - Buying A House |
67A - Partial Teacher | 116A - Tram |
1472B - Fair Division | 1281C - Cut and Paste |
141A - Amusing Joke | 112A - Petya and Strings |
677A - Vanya and Fence | 1621A - Stable Arrangement of Rooks |
472A - Design Tutorial Learn from Math | 1368A - C+= |
450A - Jzzhu and Children | 546A - Soldier and Bananas |
32B - Borze | 1651B - Prove Him Wrong |
381A - Sereja and Dima | 41A - Translation |
1559A - Mocha and Math | 832A - Sasha and Sticks |
292B - Network Topology | 1339A - Filling Diamonds |
910A - The Way to Home | 617A - Elephant |
48A - Rock-paper-scissors | 294A - Shaass and Oskols |