#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
const int maxn = 505;
long long a[maxn], b[maxn], c[maxn], p[maxn];
long long dp[maxn][maxn] = {};
struct FastMod {
  __int128_t bb, m;
  FastMod(long long b2)
      : bb(b2), m((__int128_t)(((__int128_t)(1) << 64) / b2)) {}
  inline long long reduce(long long aa) {
    __int128_t q = (__int128_t)(((__int128_t)(m)*aa) >> 64);
    __int128_t r = aa - q * bb;
    return r >= bb ? r - bb : r;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n, k;
  cin >> n >> k;
  FastMod f(k);
  for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
  for (int i = n; i >= 0; i--) {
    c[i] = a[i] + b[i];
    p[i] = c[i] + (i == n - 1 ? 0 : p[i + 1]);
  }
  for (int i = 0; i < n; i++)
    for (int x = 0; x < k; x++) {
      int y = f.reduce(p[i + 1] - x);
      if (y < 0) continue;
      long long ck = f.reduce(c[i]);
      long long mx = 0;
      long long bnd = min(k, a[i] + 1);
      for (int dx = 0; dx < bnd; dx++) {
        int dy = f.reduce(c[i] - dx);
        if (dy > b[i]) continue;
        mx = max(mx, dp[i][f.reduce(x + dx)] + (x + dx >= k) + (y + dy >= k) -
                         (dx + dy > ck));
      }
      dp[i + 1][x] = mx + c[i] / k;
    }
  cout << dp[n][0] << "\n";
}
