#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-' ? -1 : f, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
int buf[30];
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  for (; x; x /= 10) buf[++buf[0]] = x % 10;
  if (!buf[0]) buf[++buf[0]] = 0;
  for (; buf[0]; putchar('0' + buf[buf[0]--]))
    ;
}
const int INF = INT_MAX >> 1;
const int N = 205;
const int T = 205;
const int V = N << 1;
const int K = 5005;
const int E1 = K + N + N;
const int E2 = (E1 * 3 + 1) << 1;
inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }
int ans[N][N];
int deg[2][N];
int pos[K][2];
int eid[K];
int sum[T];
int n, m, t, cost, t_, k;
struct network {
  int tov[E2], nxt[E2], f[E2], v[E2], r[E2];
  int last[V], lab[V];
  int S, T, SS, TT, tot;
  queue<int> q;
  inline void init() {
    memset(last, 0, sizeof last), memset(tov, 0, sizeof tov),
        memset(nxt, 0, sizeof nxt);
    tot = 0, S = 0, T = n + m + 1, SS = T + 1, TT = SS + 1;
  }
  inline void insert(int x, int y, int full, int rev) {
    tov[++tot] = y, nxt[tot] = last[x], f[tot] = full, v[tot] = 0,
    r[tot] = tot + rev, last[x] = tot;
  }
  inline int addedge(int x, int y, int full) {
    return insert(x, y, full, 1), insert(y, x, 0, -1), r[tot];
  }
  inline int build(int x, int y, int L, int U) {
    return addedge(SS, y, L), addedge(x, TT, L), addedge(x, y, U - L);
  }
  inline bool relabel() {
    for (int x = S; x <= TT; ++x) lab[x] = 0;
    for (lab[SS] = 1, q.push(SS); !q.empty(); q.pop())
      for (int x = q.front(), i = last[x], y; i; i = nxt[i])
        if (!lab[y = tov[i]] && f[i] - v[i]) lab[y] = lab[x] + 1, q.push(y);
    return lab[TT];
  }
  int aug(int x, int flow) {
    if (x == TT) return flow;
    int ret = 0;
    for (int i = last[x], y; i; i = nxt[i])
      if (lab[y = tov[i]] == lab[x] + 1 && f[i] - v[i]) {
        int tmp = aug(y, min(flow, f[i] - v[i]));
        if (tmp) {
          ret += tmp, flow -= tmp;
          v[i] += tmp, v[r[i]] -= tmp;
          if (!flow) break;
        } else
          lab[y] = 0;
      }
    return ret;
  }
  inline int maxflow() {
    int ret = 0;
    for (int tmp; relabel();)
      for (; tmp = aug(SS, INF); ret += tmp)
        ;
    return ret;
  }
} net;
void assign(int t) {
  net.init();
  for (int i = 1; i <= n; ++i) deg[0][i] = 0;
  for (int i = 1; i <= m; ++i) deg[1][i] = 0;
  for (int i = 1, x, y; i <= k; ++i)
    if (!ans[x = pos[i][0]][y = pos[i][1]])
      ++deg[0][x], ++deg[1][y], eid[i] = net.build(x, y + n, 0, 1);
  for (int i = 1; i <= n; ++i)
    net.build(net.S, i, (int)floor((1. * deg[0][i]) / (1. * t)),
              (int)ceil((1. * deg[0][i]) / (1. * t)));
  for (int i = 1; i <= m; ++i)
    net.build(n + i, net.T, (int)floor((1. * deg[1][i]) / (1. * t)),
              (int)ceil((1. * deg[1][i]) / (1. * t)));
  net.addedge(net.T, net.S, INF), net.maxflow();
  for (int i = 1, x, y; i <= k; ++i)
    if (!ans[x = pos[i][0]][y = pos[i][1]])
      if (net.f[eid[i]] == net.v[eid[i]]) ans[x][y] = t;
}
int main() {
  n = read(), m = read(), k = read(), t = read();
  for (int i = 1; i <= k; ++i) pos[i][0] = read(), pos[i][1] = read();
  for (t_ = t; t_; --t_) assign(t_);
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= t; ++j) sum[j] = 0;
    for (int j = 1; j <= m; ++j) ++sum[ans[i][j]];
    int mx = 0;
    for (int j = 1; j <= t; ++j)
      for (int k = 1; k <= t; ++k) mx = max(mx, sum[j] - sum[k]);
    cost += mx;
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= t; ++j) sum[j] = 0;
    for (int j = 1; j <= n; ++j) ++sum[ans[j][i]];
    int mx = 0;
    for (int j = 1; j <= t; ++j)
      for (int k = 1; k <= t; ++k) mx = max(mx, sum[j] - sum[k]);
    cost += mx;
  }
  write(cost), putchar('\n');
  for (int i = 1; i <= k; ++i)
    write(ans[pos[i][0]][pos[i][1]]), putchar("\n "[i < k]);
  return 0;
}
