#include <bits/stdc++.h>
using namespace std;
inline int qr() {
  int f = 0, fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fu = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + c - 48;
    c = getchar();
  }
  return f * fu;
}
const int N = 505;
long long f[N][N], sum[N];
int a[N], b[N];
int n, k;
int main() {
  n = qr(), k = qr();
  for (register int i = 1; i <= n; ++i)
    a[i] = qr(), b[i] = qr(), sum[i] += sum[i - 1] + a[i] + b[i];
  memset(f, -1, sizeof(f));
  f[0][0] = 0;
  for (register int i = 0; i <= n - 1; ++i)
    for (register int j = 0; j <= k - 1; ++j)
      if (f[i][j] >= 0) {
        long long num1 = j + a[i + 1],
                  num2 = sum[i] + b[i + 1] - k * f[i][j] - j;
        f[i + 1][num1 % k] =
            max(f[i + 1][num1 % k], f[i][j] + num1 / k + num2 / k);
        for (register int l = max(1, k - b[i + 1]); l <= min(a[i + 1], k - 1);
             ++l)
          f[i + 1][(num1 - l) % k] =
              max(f[i + 1][(num1 - l) % k],
                  f[i][j] + (num1 - l) / k + (num2 - (k - l)) / k + 1);
      }
  long long ans = 0;
  for (register int i = 0; i <= n; ++i)
    for (register int j = 0; j <= k - 1; ++j) ans = max(ans, f[i][j]);
  printf("%lld\n", ans);
  return 0;
}
