#include <bits/stdc++.h>
using namespace std;
const int oo = 2139063143;
const int N = 510;
const int P = 1000000007;
const double eps = 1e-7;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = getchar();
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
template <typename T1, typename T2>
void chkmax(T1 &A, T2 B) {
  A = A >= B ? A : B;
}
template <typename T1, typename T2>
void chkmin(T1 &A, T2 B) {
  A = A <= B ? A : B;
}
int n, k, f[N][N], a[N], b[N];
int main() {
  sc(n), sc(k);
  long long sa = 0, sb = 0;
  for (int i = 1; i <= n; i++) sc(a[i]), sc(b[i]), sa += a[i], sb += b[i];
  int A = sa % k, B = sb % k;
  long long ans = (sa + sb) / k;
  if (A + B < k) return pr(ans), 0;
  f[0][0] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < k; j++)
      if (f[i][j])
        for (int x = 0; x <= min(k, a[i + 1]); x++)
          if ((k - x) % k <= b[i + 1]) f[i + 1][(j + x) % k] = 1;
  for (int i = 0; i < k; i++)
    if (f[n][i] && (sa - i) % k + (sb + i) % k < k) return pr(ans), 0;
  pr(ans - 1);
  return 0;
}
