java 前缀和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long s = sc.nextLong();
        int t = 0;          // 记录所有士兵中最大的训练次数
        long ans = 0;           // 总费用
        long cost = 0;      // 当前需要单独训练的士兵总费用
        int N = 10000000 + 10;
        long[] a = new long[N]; // a[i] 表示第i次训练时满级的士兵费用总和
        for (int i = 0; i < n; i++) {
            int p = sc.nextInt();
            int c = sc.nextInt();
            cost += p;       // 初始总费用包含所有士兵的第一次训练
            a[c] += p;           // 记录在c次训练后满级的士兵费用
            t = Math.max(t, c); // 更新最大训练次数
        }
        // 遍历每次训练决策
        for (int i = 1; i <= t; i++) {
            // 选择当前训练方式：组团 or 单独
            if (cost > s) {
                ans += s;       // 组团更划算
            } else {
                ans += cost; // 单独训练更划算
            }
            // 移除已经满级的士兵费用
            cost -= a[i];    // 第i次训练后，达到训练次数的士兵不再参与后续训练
        }

        System.out.println(ans);
    }
}