#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
int dp[2][MAXN];
void solve() {
  int n, k;
  scanf("%d%d", &n, &k);
  int *x = dp[0];
  int *y = dp[1];
  x[0] = 1;
  y[0] = 1;
  long long sa = 0, sb = 0;
  for (int i = 0; i < n; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    sa += a;
    sb += b;
    int jm = max(k - b, 0);
    int jM = min(k - 1, a);
    for (int z = 0; z < k; ++z) {
      if (x[z]) {
        for (int j = jm; j <= jM; ++j) y[(j + z) % k] = 1;
      }
    }
    for (int j = 0; j < k; ++j) x[j] = y[j];
  }
  long long res = 0;
  for (int j = 0; j < k; ++j) {
    if (x[j]) {
      long long aa = sa - j;
      while (aa < 0) aa += k;
      long long bb = (sa + sb) - aa;
      res = max(res, (aa / k) + (bb / k));
    }
  }
  printf("%I64d\n", res);
}
int main() {
  solve();
  return 0;
}
