#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 7;
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n), b(n);
  vector<bool> can(k);
  long long sum1 = 0, sum2 = 0;
  for (long long i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    sum1 += a[i];
    sum2 += b[i];
  }
  can[sum1 % k] = true;
  for (long long i = 0; i < n; i++) {
    long long Max = min(a[i], k);
    long long Min = k - min(b[i], k);
    Max = -Max + k, Min = -Min + k, swap(Max, Min);
    vector<bool> new_can(k);
    for (long long j = 0; j < k; j++) new_can[j] = can[j];
    for (long long q = 0; q < k; q++) {
      if (can[q]) {
        for (long long j = Min; j <= Max; j++) {
          new_can[(q + j) % k] = true;
        }
      }
    }
    can = new_can;
  }
  long long Min = inf;
  for (long long i = k - 1; i >= 0; i--)
    if (can[i]) Min = i;
  sum2 += (sum1 % k - Min);
  sum1 -= (sum1 % k - Min);
  cout << (sum1 / k + sum2 / k);
}
