#include <bits/stdc++.h>
using namespace std;
void shikhar7s(long long int cas) {
  long long int n, k, i;
  cin >> n >> k;
  long long int a[n], b[n], s = 0;
  for (i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    s += a[i];
    s += b[i];
  }
  long long int dp[n + 1][k], j, l;
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (i = 0; i < n; i++) {
    for (l = 0; l < min(k, a[i] + 1); l++) {
      if (!((a[i] - l) % k) || ((a[i] - l) % k) + b[i] >= k) {
        for (j = 0; j < k; j++) {
          if (dp[i][j]) {
            dp[i + 1][(j + l) % k] = 1;
          }
        }
      }
    }
  }
  long long int ans = 0;
  for (i = 0; i < k; i++) {
    if (dp[n][i]) {
      ans = max(ans, (s - i - ((s - i) % k)) / k);
    }
  }
  cout << ans;
}
signed main() {
  std::ios_base::sync_with_stdio(false);
  long long int t = 1;
  long long int cas = 1;
  while (cas <= t) {
    shikhar7s(cas);
    cas++;
  }
  return 0;
}
