First, let us consider when the answer is infinite. It turns out that it is infinite when the total sum of \(A\) is not greater than \(M\); because the total cost required is always not greater than \(M\). Conversely, if the total sum is greater than \(M\), for example setting the upper bound to the maximum value of \(A\) exceeds the budget, so the maximum value exists.

From now on, we assume that the answer is not infinite. When it comes to finding the maximum value subject to some condition, a technique called binary search is effective.

In our case, given the upper bound \(x\), one can determine if the total cost exceeds the budged in \(O(N)\) time. The number of iterations in the binary search \(O(\log {\max{A}})\), because the upper bound of the answer is \(\max{A}\) by the aforementioned discussion for the infinite case.

Therefore, the problem can be solved in \(O(N\log {\max{A}})\) time.

Sample code (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;
}