#include <bits/stdc++.h>
using namespace std;
int N, K;
int A, B;
signed long long from[505];
signed long long to[505];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> K;
  for (x = 0; x < (505); x++)
    for (y = 0; y < (505); y++) from[x] = -1LL << 60;
  from[0] = 0;
  int sum = 0;
  for (i = 0; i < (N); i++) {
    cin >> A >> B;
    for (x = 0; x < (505); x++) to[x] = -1LL << 60;
    for (x = 0; x < (K); x++) {
      y = (sum - x) % K;
      if (y < 0) y += K;
      for (j = 0; j < (K); j++) {
        if (j > A) continue;
        k = (A + B - j) % K;
        if (k > B) continue;
        int add = (A + B - j - k) / K;
        to[(x + j) % K] = max(to[(x + j) % K],
                              from[x] + add + ((x + j) >= K) + ((y + k) >= K));
      }
    }
    (sum += A + B) %= K;
    swap(from, to);
  }
  signed long long ma = 0;
  for (i = 0; i < (K); i++) ma = max(ma, from[i]);
  cout << ma << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}
