#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, k;
  cin >> n >> k;
  vector<pair<long long, long long> > a(n);
  long long sum[2] = {0, 0};
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second;
    sum[0] += a[i].first;
    sum[1] += a[i].second;
  }
  long long res = sum[0] / k + sum[1] / k;
  sum[0] %= k;
  sum[1] %= k;
  bool dpex[505];
  bool dpnw[505];
  dpnw[0] = true;
  for (int i = 1; i < k; i++) dpnw[i] = false;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      dpex[j] = dpnw[j];
    }
    for (int j = 0; j < k; j++) {
      for (int ifirst = max(k - a[i].second, 1ll);
           ifirst <= min(k - 1, a[i].first); ifirst++) {
        if (dpex[j]) {
          dpnw[(j + ifirst) % k] = true;
        }
      }
    }
  }
  for (int i = k - sum[1]; i <= sum[0]; i++) {
    if (dpnw[i]) {
      res++;
      break;
    }
  }
  cout << res;
  return 0;
}
