#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
bool dp[505][505];
int c[505];
int N, K, a[505], b[505];
long long s1, s2;
int main() {
  ios::sync_with_stdio(false);
  cin >> N >> K;
  for (int i = 1; i <= N; ++i) cin >> a[i] >> b[i], s1 += a[i], s2 += b[i];
  dp[0][0] = 1;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) c[j] = 0, dp[i + 1][j] = dp[i][j];
    if (a[i + 1] + b[i + 1] >= K)
      for (int j = 0; j < K; ++j) {
        if (!dp[i][j]) continue;
        int l, r;
        l = max(1, K - b[i + 1]);
        r = min(K - 1, a[i + 1]);
        if (l <= r) {
          int St, Ed;
          St = j + l;
          Ed = j + r;
          St %= K;
          Ed %= K;
          c[St]++;
          if (Ed >= St) {
            c[Ed + 1]--;
          } else {
            c[0]++;
            c[Ed + 1]--;
          }
        }
      }
    for (int j = 0; j < K; ++j) {
      if (j) c[j] += c[j - 1];
      dp[i + 1][j] |= c[j];
    }
  }
  long long res = 0;
  for (int j = 0; j < K; ++j) {
    if (!dp[N][j]) continue;
    long long l1, l2;
    l1 = s1, l2 = s2;
    l1 -= j;
    l2 -= (K - j) % K;
    long long cur = bool(j) + (l1 / K) + (l2 / K);
    res = max(res, cur);
  }
  cout << res << endl;
  return 0;
}
