#include <bits/stdc++.h>
using namespace std;
int n, m, a[505], b[505], dp[505][505];
long long ans, sum;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
  for (int i = 1; i <= n; i++) sum += a[i] + b[i];
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < m; j++)
      if (dp[i - 1][j])
        for (int k = 0; k <= min(a[i], m - 1); k++)
          if ((a[i] - k) % m + b[i] >= m || (a[i] - k) % m == 0)
            dp[i][(j + k) % m] = 1;
  for (int i = 0; i < m; i++)
    if (dp[n][i]) ans = max(ans, (sum - i) / m);
  printf("%lld\n", ans);
  return 0;
}
