#include <bits/stdc++.h>
using namespace std;
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
  return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) {
  return pair<S, T>(s.first - t.first, s.second - t.second);
}
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
const long long inf = 1000000001;
const long long INF = (long long)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
vector<int> dx2 = {1, 1, 0, -1, -1, -1, 0, 1},
            dy2 = {0, 1, 1, 1, 0, -1, -1, -1};
const long long MOD = 1000000007;
long long dp[501][500];
int r[500], b[500];
void solve() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < (int)(n); i++) {
    scanf("%d %d", &r[i], &b[i]);
  }
  for (int i = 0; i < (int)(n + 1); i++)
    for (int j = 0; j < (int)(k); j++) dp[i][j] = -INF;
  dp[0][0] = 0;
  int ha = 0;
  for (int i = 0; i < (int)(n); i++) {
    for (int j = 0; j < (int)(k); j++) {
      if (dp[i][j] == -INF) continue;
      int bj = (ha - j + k) % k;
      for (int u = 0; u < (int)(k); u++) {
        if (u > r[i]) break;
        int nokori = r[i] - u + b[i];
        int add = nokori / k;
        int v = nokori - add * k;
        if (v > b[i]) continue;
        int nj = (j + u) % k;
        if (j + u >= k) add++;
        if (bj + v >= k) add++;
        chmax(dp[i + 1][nj], dp[i][j] + add);
      }
    }
    ha += (r[i] + b[i]) % k;
    if (ha > k) ha -= k;
  }
  long long ans = 0;
  for (int i = 0; i < (int)(k); i++) chmax(ans, dp[n][i]);
  printf("%lld\n", ans);
}
signed main() {
  int t;
  t = 1;
  while (t--) {
    solve();
  }
}
