二分探索を行わない方針を示します。
問題文中にも言及がある通り、オーバーフローに十分注意して実装する必要があります。
ひとつの解決策は、 Python のように十分な桁数がある多倍長整数を持つ言語で実装することです。
本実装例では、 \(64\)bit 符号付き整数内で全ての処理を完了させます。

まず、答えが -1 かどうか判定します。

\(h=M\) から始めて、 \(h=\max(0,h-R_i)\) で置き換えることを繰り返します。
このとき、終了時に \(h=0\) であることと \(\sum R_i \ge M\) であることとは同値です。また、オーバーフローの心配もありません。

次に、不公平度を最小化する割り当てを求めます。
不公平度 \(x\) を決め打った時、スタッフ \(i\) には \(\max(0,R_i-x)\) 個以上の仕事を割り当てる必要があります。
この不公平度を徐々に下げながら仕事を割り当てることを考えます。
直感的には、 \(R_i \ge x\) となったタイミングでスタッフ \(i\) にシフトを割り当て始めるイメージです。
以下を割り当てるシフトが尽きるまで繰り返します。

• 不公平度を \(x\) から \(x-1\) に下げることを考える。
• このとき、 \(R_i \ge x\) なるスタッフ \(i\) 全員にシフトを \(1\) つ割り当てる必要がある。

これをそのまま実装すると \(O(M)\) かかってしまいますが、シフトを割り当てるスタッフの集合が変わらないうちは、簡単な計算によって \(x\) の引き下げをまとめて行うことができます。
適切に計算することで、値域も \(64\)bit 符号付き整数の範疇に収めることができます。詳しくは実装例を参照してください。

結局、時間計算量 \(O(N \log N)\) でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M;
  cin >> N >> M;
  ll chk=M;
  vector<ll> R(N);
  map<ll,ll> mp;
  for(auto &nx : R){
    cin >> nx;
    chk=max(0ll,chk-nx);
    mp[-nx]++;
  }
  mp[0]+=0;
  if(chk>0){cout << "-1\n"; return 0;}
  ll pre=-2e18,cnt=0;
  for(auto &nx : mp){
    if(cnt>0){
      ll dist=(nx.first-pre);
      ll leap=min(dist,M/cnt);
      M-=leap*cnt;
      if(!(leap==dist && M>0)){
        cout << (-pre)-leap << "\n";
        return 0;
      }
    }
    pre=nx.first;
    cnt+=nx.second;
  }
  cout << "0\n";
  return 0;
}