思路与算法

购买每种糖果的数量拆成若干对和至多一个额外奇数颗。任一对花x_i+y_i，统一用最便宜的一对C。把x_i排序并做前缀和P_r，枚举额外奇数颗来自r种不同糖果：若P_r≤预算m，可买r+2*floor((m-P_r)/C)颗，取最大。

正确性说明

任意购买方案都可唯一按每种的奇偶性拆分。固定r时，r颗额外糖必须来自不同种，费用至少最小r个x之和；所有完整对费用至少C，所以公式给上界。反过来取这r种各一颗，并把所有对购买于达到C的种类；该种即使已有额外一颗，2t+1颗总价仍为tC+x，不违反交替价格。故公式可实现，枚举全部r得到全局最优。

复杂度

O(n log n)时间、O(n)空间，含读入、排序和前缀累计初始化。

易错点

不能把偶数便宜颗单独买。r=0必须枚举，预算达1e18用64位；所有价格为正，答案不会超过预算。

参考代码（C++11）

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

int main() {
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> x(n);
    long long pairCost = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        long long y;
        cin >> x[i] >> y;
        pairCost = min(pairCost, x[i] + y);
    }
    sort(x.begin(), x.end());
    long long ans = (m / pairCost) * 2, sum = 0;
    for (int i = 0; i < n; i++) {
        sum += x[i];
        if (sum > m)
            break;
        ans = max(ans, i + 1 + (m - sum) / pairCost * 2);
    }
    cout << ans << "\n";
}