#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
const int mod = 1e9 + 7;
long long qpow(long long a, long long b) {
  long long res = 1;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
bool dp[maxn][maxn];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  dp[0][0] = 1;
  long long tot = 0;
  for (int i = 1, a, b; i <= n; ++i) {
    scanf("%d%d", &a, &b);
    tot += a + b;
    for (int j = 0; j < k; ++j) {
      int tmp = a % k;
      dp[i][j] |= dp[i - 1][(j - tmp + k) % k];
      for (int p = 0; p <= min(a, k - 1); ++p) {
        if ((a - p) % k + b >= k) dp[i][j] |= dp[i - 1][(j - p + k) % k];
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < k; ++i) {
    if (dp[n][i]) ans = max(ans, (tot - i) / k);
  }
  cout << ans << endl;
  return 0;
}
