发工资

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


class Money {
    int value;
    int nums;

    public Money(int value, int nums) {
        this.value = value;
        this.nums = nums;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Money> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.add(new Money(a, b));
        }
        list.sort((a, b) -> b.value - a.value);
        int ans = 0;
        //先把大的直接发出去
        for (Money money : list) {
            if (money.value >= m) {
                ans += money.nums;
                money.nums = 0;
            } else break;
        }

        //然后开始车轮战，每一趟while发出一个月工资
        while (true) {
            int needToPay = m;
            //先从大面额开始涮一轮，在不超m的情况下，尽可能地拿大面额
            for (Money money : list) {
                if (money.nums == 0) continue;
                int needNum = needToPay / money.value;
                needNum = Math.min(needNum, money.nums);//最多取完，不能超了。
                money.nums -= needNum;
                needToPay -= needNum * money.value;
            }
            //刚好凑成了就结束这一趟
            if (needToPay <= 0) {
                ans++;
                continue;
            }
            //再从小面额开始补（此时所有面额都已大于needToPay）
            for (int i = list.size() - 1; i >= 0; i--) {
                Money money = list.get(i);
                if (money.nums == 0) continue;
                money.nums--;
                needToPay -= money.value;
                ans++;
                break;
            }
            if (needToPay > 0) break;
        }
        System.out.println(ans);
    }
}

import java.util.*;
import java.io.*;

class Money{
    public int value;//钞票面额
    public int num;//该面额钞票的数量
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        Money[] a = new Money[n];
        for(int i = 0; i < n; i++){
            s = in.readLine().split(" ");
            a[i] = new Money();
            a[i].value = Integer.parseInt(s[0]);
            a[i].num = Integer.parseInt(s[1]);
        }
        Arrays.sort(a, new Comparator<Money>(){//将钞票按从大到小排列
            public int compare(Money a1, Money a2){
                return a2.value - a1.value; 
            }
        });
        int large = 0;//用于后续直接从面额小于工资的钞票开始遍历
        int month = 0;//能发工资的月份
        //将面额大于等于工资的钞票全部取出直接发工资
        while(large < n && a[large].value >= m){
            month += a[large].num;
            a[large].num = 0;
            large++;
        }
        //处理面额小于工资的钞票
        while(true){
            int npay = m;//记录一个月还需要支付多少工资
            //先从面额大的开始取，取到刚好不超过工资数量
            for(int i = large; i < n; i++){
                if(a[i].num == 0) continue;
                int pNum = npay / a[i].value;//记录某个面额钞票能够补的数量
                pNum = Math.min(pNum, a[i].num);//不能超过钞票剩余数量
                npay -= pNum * a[i].value;
                a[i].num -= pNum;
                if(npay <= 0) break;//刚好取到工资的数量，直接跳出循环
            }
            //如果刚好取到了工资的数量，就直接发工资
            if(npay <= 0){
                month++;
                continue;
            }
            //再从面额小的开始补工资
            for(int i = n-1; i >= large; i--){
                if(a[i].num == 0) continue;
                while(npay > 0 && a[i].num > 0){
                    npay -= a[i].value;
                    a[i].num--;
                }
                if(npay <= 0){//工资补够了，跳出循环
                    month++;
                    break;
                }
            }
            if(npay > 0) break;//钞票都补完了还没补够，没救了
        }
        System.out.println(month);
    }
}

#include <bits/stdc++.h>

typedef std::pair<int, int> PAII;
using namespace std;

struct Money {
    long long x;
    int y;

    bool operator<(Money m2) const {
        return x < m2.x;
    }
};

istream &operator>>(istream &is, Money &money) {
    is >> money.x >> money.y;
    return is;
}

int main() {
    int n;
    long long m;
    cin >> n >> m;
    long long totalSum = 0L;
    vector<Money> moneyGroup(n);
    unordered_map<int,int> modMoney;

    for (int i = 0; i < n; ++i) {
        cin >> moneyGroup[i];
        totalSum += moneyGroup[i].x * moneyGroup[i].y;
    }
    if (totalSum < m) {
        cout << 0 << endl;
    } else {

        sort(moneyGroup.begin(), moneyGroup.end());

        long long ans = 0;
        while (1) {
            long long rest = m;
            for (int i = n - 1; i >= 0 && rest > 0; --i) {
                if (moneyGroup[i].y == 0)
                    continue;
                // 有个整除关系感觉没用到。
                // 先用大钱的思路没错，但是用小钱补的时候，小钱能提供更多的容错率

                auto need = rest / moneyGroup[i].x;
                if (need > moneyGroup[i].y) {
                    need = moneyGroup[i].y - 1;
                }
                rest -= need * moneyGroup[i].x;
                moneyGroup[i].y -= need;
            }

            for (int i = 0; i < n && rest > 0; ++i) {
                if (moneyGroup[i].y == 0)
                    continue;
                auto need = max((int)(rest / moneyGroup[i].x),1);
                if (need > moneyGroup[i].y) {
                    need = moneyGroup[i].y;
                }

                rest -= need * moneyGroup[i].x;
                moneyGroup[i].y -= need;
            }
            if (rest > 0)
                break;
            ++ans;
        }
        cout << ans;
    }
}