#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
inline int read() {
  char c = getchar();
  int x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
int n, m, k;
long long f[505][505], sum;
signed main() {
  memset(f, -63, sizeof f);
  f[0][0] = 0;
  n = read(), k = read();
  for (register int i = (1); i <= (n); ++i) {
    int a = read(), b = read();
    for (register int j = (0); j <= (k - 1); ++j) {
      int tmp = (sum + k - j) % k;
      for (int l = 0; l < min(k, a + 1); l++) {
        int tmp2 = ((a + b) % k + k - l) % k;
        if (tmp2 > b) continue;
        f[i][(j + l) % k] = max(f[i][(j + l) % k], f[i - 1][j] + (j + l) / k +
                                                       (tmp + tmp2) / k +
                                                       (a + b - tmp2 - l) / k);
      }
    }
    sum += a + b;
    sum %= k;
  }
  long long res = 0;
  for (register int i = (0); i <= (k - 1); ++i) res = max(res, f[n][i]);
  cout << res;
  return 0;
}
