#include <stdio.h>
#define N 2000
#define M (1 << 20)
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int cc[M];
long long ss[M];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (cc[hh[j]] == cc[h] && ss[hh[j]] == ss[h])
j++;
else if (cc[hh[j]] > cc[h] || cc[hh[j]] == cc[h] && ss[hh[j]] < ss[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int main() {
static int ww[N], qu[N][N], cnt[N], hh[M];
static char available[N];
int n, m, k, h, i, d, b, c, c_;
long long s, s_;
scanf("%d%d", &n, &k);
for (i = 0; i < n; i++) {
scanf("%d%d", &ww[i], &d), d--;
qu[d][cnt[d]++] = i;
}
if (n <= 20) {
m = 0;
for (b = 0; b < 1 << n; b++) {
c = s = 0;
for (d = 0; d < n; d++)
for (h = 0; h < cnt[d]; h++)
if ((b & 1 << qu[d][h]) != 0) {
c++, s += ww[qu[d][h]];
if (c > d + 1) {
c = -1;
goto out;
}
}
out:
if (c != -1)
cc[m] = c, ss[m] = s, m++;
}
for (h = 0; h < m; h++)
hh[h] = h;
sort(hh, 0, m);
for (h = 0; h < k; h++)
printf("%d %lld\n", cc[hh[h]], ss[hh[h]]);
} else {
c_ = 0, s_ = 0;
for (d = n - 1, c = 0; d >= 0; d--) {
for (h = 0; h < cnt[d]; h++)
available[qu[d][h]] = 1, c++;
if (c > 0) {
int i_;
i_ = -1;
for (i = 0; i < n; i++)
if (available[i] && (i_ == -1 || ww[i_] > ww[i]))
i_ = i;
available[i_] = 0, c--;
c_++, s_ += ww[i_];
}
}
printf("%d %lld\n", c_, s_);
}
return 0;
}
