#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
long long a, b, n, k;
long long dp[maxn][maxn];
int main() {
  cin >> n >> k;
  long long kq = 0, tg;
  dp[0][0] = 1;
  for (long long i = 1; i <= n; i++) {
    cin >> a >> b;
    kq += a + b;
    for (long long x = 0; x <= k - 1; x++) {
      if (dp[i - 1][x] == 1) {
        for (long long r = 0; r <= min(a, k - 1); r++) {
          if ((a - r) % k + b >= k || (a - r) % k == 0) dp[i][(x + r) % k] = 1;
        }
      }
    }
  }
  for (long long x = 0; x <= k - 1; x++) {
    if (dp[n][x] == 1) {
      tg = x;
      break;
    }
  }
  kq = (kq - tg) / k;
  cout << kq;
}
