// 演算法 / Algorithm:
// 用計數排序統計每個價格出現幾次，再從最便宜的價格開始貪心地買，
// 只要錢夠就一直買，直到買不起為止。
// Counting-sort the prices, then greedily buy from the cheapest price up,
// purchasing as many as the remaining coins allow until we can't afford one.

#define MAX_COST 100000  // 價格上限 / the maximum possible price (per constraints)

int maxIceCream(int* costs, int costsSize, int coins) {
    // cnt[p] 將記錄價格剛好為 p 的冰淇淋有幾支
    // cnt[p] will hold how many bars cost exactly p.
    // 大小要 MAX_COST+1 因為索引從 0 用到 MAX_COST / size is MAX_COST+1 so index MAX_COST is valid.
    // 陣列初始化為全 0：{0} 會把第一個元素設 0，其餘自動補 0。
    // {0} zero-initializes the whole array (first element 0, the rest filled with 0).
    int cnt[MAX_COST + 1] = {0};

    // 第一遍：把每支冰淇淋丟進對應價格的「桶子」計數
    // First pass: drop each bar into the bucket for its price and count it.
    for (int i = 0; i < costsSize; i++) {
        cnt[costs[i]]++;  // costs[i] 是價格，當作索引；++ 表示該桶數量加一 / use the price as an index; ++ increments that bucket
    }

    int bars = 0;  // 已買的冰淇淋數量，也是最終答案 / number of bars bought so far = the answer

    // 第二遍：價格由小(1)到大(MAX_COST)掃描，先買便宜的
    // Second pass: sweep prices from cheapest (1) to most expensive, buying cheap first.
    for (int p = 1; p <= MAX_COST; p++) {
        // 對價格 p 的每一支冰淇淋，嘗試購買
        // For each bar that costs p, try to buy it.
        for (int k = 0; k < cnt[p]; k++) {
            if (coins < p) {
                // 連最便宜（當前 p）的都買不起，後面更貴的更不可能，直接回傳答案
                // Can't even afford price p; everything ahead is pricier, so we're done.
                return bars;
            }
            coins -= p;  // 付錢：剩餘硬幣減去這支的價格 / pay: subtract this bar's price from coins
            bars++;      // 成功買到一支 / one more bar bought
        }
    }

    // 走到這裡代表所有冰淇淋都買得起（錢有剩或剛好）
    // Reaching here means we could afford every bar.
    return bars;
}