#include <bits/stdc++.h>
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  for (; c > '9' || c < '0'; c = getchar()) {
    if (c == '-') f = -1;
  }
  for (; c >= '0' && c <= '9'; c = getchar()) {
    x = x * 10 + c - '0';
  }
  return x * f;
}
long long dp[505][505];
int a[505], b[505];
inline void work() {
  int n = read(), k = read();
  memset(dp, -1, sizeof dp);
  long long sum = 0, ans = 0;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    a[i] = read(), b[i] = read();
    for (int j = 0; j < k; j++) {
      if (dp[i - 1][j] < 0) continue;
      int l = sum - 1ll * dp[i - 1][j] * k - j;
      for (int s1 = 0; s1 <= a[i] && s1 < k; s1++) {
        if (b[i] + s1 >= k) {
          int a2 = j + a[i] - s1, b2 = l + b[i] - (k - s1);
          dp[i][a2 % k] =
              std::max(dp[i][a2 % k], dp[i - 1][j] + a2 / k + b2 / k + 1);
        }
      }
      dp[i][(j + a[i]) % k] =
          std::max(dp[i][(j + a[i]) % k],
                   dp[i - 1][j] + (j + a[i]) / k + (l + b[i]) / k);
    }
    sum += a[i] + b[i];
  }
  for (int j = 0; j < k; j++) {
    ans = std::max(ans, dp[n][j]);
  }
  printf("%lld\n", ans);
}
int main() {
  work();
  return 0;
}
