1

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
ll n,w,a[N],maxn,minn;
int main(){
	cin >> n >> w;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		maxn += max(i > 1 ? a[i - 1] - a[i] : -1,a[i]);
	}
	stable_sort(a + 1,a + 1 + n);
	minn += a[1];
	for (int i = 2;i <= n;i++){
		minn += min(a[i] - a[i - 1],a[i]);
	}
	cout << minn << ' ' << maxn;
	return 0;
}

2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
ll n,w,a[N],maxn,minn,partsize;
bool chk[N];
vector <int> part[N];
int main(){
	cin >> n >> w;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	stable_sort(a + 1,a + 1 + n);
	for (int i = 1;i <= n;i++){
		if (chk[i])continue;
		++partsize;
		chk[i] = 1;
		part[partsize].push_back(a[i]);
		for (int j = i + 1;j <= n;j++){
			if (chk[j])continue;
			if (part[partsize].back() * 2 < a[j]){
				chk[j] = 1;
				part[partsize].push_back(a[j]);
			}
		}
	}
	/*
	for (int i = 1;i <= partsize;i++){
		for (int j = part[i].size() - 1;j >= 0;j--){
			cout << part[i][j] << ' ';
		}
		cout << '\n';
	}
	*/
	for (int i = 1;i <= partsize;i++){
		maxn += part[i][part[i].size() - 1];
		for (int j = part[i].size() - 2;j >= 0;j--){
			maxn += part[i][j + 1] - part[i][j];
		}
	}
	minn += a[1];
	for (int i = 2;i <= n;i++){
		minn += min(a[i] - a[i - 1],a[i]);
	}
	cout << minn << ' ' << maxn;
	return 0;
}