#include using namespace std; typedef long long LL; int main() { // 1. 入力情報取得. LL B, N; cin >> B >> N; map m; for(int i = 0; i < N; i++){ LL c; cin >> c; m[c]++; } // 2. キャンディーの総数を計算. LL candy = 0, ans = 1e11; for(auto &p : m) candy += p.first * p.second; // 3. キャンディーの配分個数を二分探索. // 配分個数: (最小): l, (最大): h. // LL l = 0, h = max(1LL, (candy + B) / N); LL l = 0, h = (candy + B) / N; if(h == 0) ans = candy; while(l < h){ // 操作回数: (最小): ol, (最大): oh. LL ol = 0, oh = 0; for(auto &p : m) ol += abs(p.first - l) * p.second, oh += abs(p.first - h) * p.second; // cout << "l=" << l << " ol=" << ol << " h=" << h << " oh=" << oh << endl; // キャンディーの配分個数を更新. if(ol < oh){ if(ans >= ol) ans = ol; h = (h + l) / 2, l++; }else{ if(ans >= oh) ans = oh; l = (h + l) / 2, h--; } } // 3. 出力. cout << ans << endl; return 0; }