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

public class addict_as {
    public static final int MAXD = 10000;

    public void run() throws IOException {
        Scanner in = new Scanner(new File("addict.in"));
        int n = in.nextInt();
        int d = in.nextInt();
        Addiction[] a = new Addiction[n];
        for (int i = 0; i < n; i++) {
            a[i] = new Addiction(in.next(), in.nextInt());
        }
        in.close();

        Arrays.sort(a);

        boolean[] can = new boolean[MAXD + 1];
        int[] need = new int[MAXD + 1];
        can[0] = true;
        need[0] = 0;
        int maxd = 0;

        int[] time = new int[n];
        Arrays.fill(time, -1);

        long ans = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= d && a[i].s - j >= 0; j++) {
                if (can[a[i].s - j] && (time[i] == -1 || time[i] > need[a[i].s - j] + 1)) {
                    time[i] = need[a[i].s - j] + 1;
                }
            }
            if (time[i] != -1) {
                ans += time[i];
                count++;
                a[i].abandon = true;

                for (int j = Math.min(maxd + a[i].s, MAXD); j >= a[i].s; j--) {
                    if (can[j - a[i].s]) {
                        if (!can[j] || need[j] > need[j - a[i].s] + time[i]) {
                            can[j] = true;
                            maxd = Math.max(maxd, j);
                            need[j] = need[j - a[i].s] + time[i];
                        }
                    }
                }
            }
        }

        PrintWriter out = new PrintWriter(new File("addict.out"));
        out.println(count + " " + ans);
        Arrays.sort(a, new Comparator<Addiction>() {
            public int compare(Addiction o1, Addiction o2) {
                return o1.name.compareTo(o2.name);
            }
        });
        for (Addiction ad : a) {
            if (ad.abandon) {
                out.println(ad.name);
            }
        }
        out.close();
    }

    class Addiction implements Comparable<Addiction> {
        String name;
        int s;
        boolean abandon;

        public Addiction(String name, int s) {
            this.name = name;
            this.s = s;
        }

        public int compareTo(Addiction o) {
            return s - o.s;
        }
    }

    public static void main(String[] args) throws IOException {
        new addict_as().run();
    }
}