まず、答えが infinite になる条件を確認しましょう。これは、\(A\) の総和が \(M\) 以下であるときです。何故ならば、このような場合かかる金額の総和は必ず \(M\) 以下であるからです。逆に、総和が \(M\) 以下の場合、例えば上限額を \(A\) の最大値に設定すれば予算を超過するので、上限額の最大値が存在することが分かります。

以下、答えが infinite でない場合を考えます。このように、条件を満たす数値の最大値を求める問題では二分探索と呼ばれる手法が有効です。

今回の問題でも、\(x\) を決め打ったとき、かかる金額の総和が予算以下であるかは \(O(N)\) で判定することができます。二分探索のイテレーション回数は、答えの上界が先程の infinite の議論より \(\max{A}\) なので、\(O(\log {\max{A}})\) 回であることがわかります。

以上よりこの問題を \(O(N\log {\max{A}})\) 時間で解くことができます。

実装例 (C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    ll m;
    cin >> n >> m;
    vector<int> a(n);
    for(auto &v : a) cin >> v;
    ll s = accumulate(a.begin(), a.end(), 0ll);
    if(s <= m) {
        cout << "infinite" << endl;
        return 0;
    }
    int ok = 0, ng = 1000000000;
    while(abs(ok - ng) > 1) {
        int mid = (ok + ng) >> 1;
        ll tmp = 0;
        for(auto v : a) tmp += min(mid, v);
        if(tmp <= m)
            ok = mid;
        else
            ng = mid;
    }
    cout << ok << endl;
}