#include <bits/stdc++.h>
using namespace std;
int dp[501][501];
long long ar[501][2];
int n, k;
int rek(int cur, int leftRed) {
  if (cur == -1) return leftRed == 0;
  if (dp[cur][leftRed] == -1) {
    dp[cur][leftRed] = rek(cur - 1, ((leftRed - ar[cur][0]) % k + k) % k);
    for (int ctr1 = 0; ctr1 <= k; ++ctr1) {
      if (ar[cur][0] < ctr1 || ar[cur][1] < k - ctr1) continue;
      dp[cur][leftRed] |=
          rek(cur - 1, ((leftRed - ar[cur][0] + ctr1) % k + k) % k);
      if (dp[cur][leftRed]) break;
    }
  }
  return dp[cur][leftRed];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  memset(dp, -1, sizeof(dp));
  cin >> n >> k;
  long long tot[2] = {0};
  for (int ctr1 = 0; ctr1 < n; ++ctr1)
    for (int ctr2 = 0; ctr2 < 2; ++ctr2)
      cin >> ar[ctr1][ctr2], tot[ctr2] += ar[ctr1][ctr2];
  long long rez = 0;
  for (int ctr1 = 0; ctr1 < k; ++ctr1)
    if (rek(n - 1, ctr1)) rez = max(rez, (tot[0] + tot[1] - ctr1) / k);
  cout << rez;
  return 0;
}
