[CSES] Elevator Rides

void solve()
{
    ll n, x;
    cin >> n >> x;

    vll a(n);
    rep(i, n) cin >> a[i];

    ll mx = (1LL << n);
    vll dp(mx + 1, inf), w(mx + 1, inf);
    /*
        dp[i]: min no of rides for carrying mask i
        w[i]: min weight carried in last ride given mask i have travelled
    */

    rep(i, n)
    {
        ll m = (1LL << i);
        if (a[i] <= x)
        {
            dp[m] = 1;
            w[m] = min(w[m], a[i]);
        }
    }

    rep(i, mx)
    {
        rep(j, n)
        {
            ll m = (1LL << j);
            if (m & i)
            {
                ll pmsk = (i ^ m);
                if (w[pmsk] + a[j] <= x)
                {
                    if (dp[i] == dp[pmsk])
                    {
                        w[i] = min(w[i], w[pmsk] + a[j]);
                    }
                    else if (dp[i] > dp[pmsk])
                    {
                        dp[i] = dp[pmsk];
                        w[i] = w[pmsk] + a[j];
                    }
                }
                else
                {
                    if (dp[i] == dp[pmsk] + 1)
                    {
                        w[i] = min(w[i], a[j]);
                    }
                    else if (dp[i] > dp[pmsk] + 1)
                    {
                        dp[i] = dp[pmsk] + 1;
                        w[i] = a[j];
                    }
                }
            }
        }
    }

    cout << dp[mx - 1] << "\n";
}