#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 5;
void fio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int dp[MAXN][MAXN];
int main() {
  fio();
  int n, k;
  cin >> n >> k;
  long long an = 0;
  vector<pair<long long, long long> > v;
  long long ax = 0;
  for (long long i = 0; i < (n); i++) {
    long long a, b;
    cin >> a >> b;
    v.push_back({a, b});
    ax += a + b;
  }
  for (long long i = 0; i < (n); i++)
    for (long long r = 0; r < (k); r++) {
      if ((i == 0 && r >= 1) || (i >= 1 && dp[i - 1][r] == 0)) continue;
      for (long long j = 0; j < (k); j++) {
        long long a = v[i].first, b = v[i].second;
        if ((a - j + b) % k <= b && j <= a) dp[i][(j + r) % k] = 1;
      }
    }
  long long ann = 0;
  for (long long i = 0; i < (k); i++) {
    if (dp[n - 1][i]) {
      long long j = (ax % k - i + k) % k;
      long long zz = (ax - j - i) / k;
      ann = max(zz, ann);
    }
  }
  cout << ann << endl;
  return 0;
}
