#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000000 + 7;
long long l, r, n, m, k, a, b, c, d, temp, temp1, temp2, ok, ok1, ok2, q, t,
    res, ans, sum;
long long x[200000 + 9], y[200000 + 9], dp[500 + 9][500 + 9];
vector<long long> v;
string s;
char ch;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
    cin >> y[i];
    a += x[i];
    b += y[i];
  }
  ans = 0;
  dp[0][0] = 1;
  for (int i = 0; i <= n + 1; i++)
    for (int j = 0; j < k; j++)
      if (dp[i][j] == 1) {
        res = (a - j) / k + (b - (k - j) % k) / k + int(j != 0);
        ans = max(ans, res);
        dp[i + 1][j] = 1;
        l = max(0ll, k - y[i]);
        r = min(k, x[i]);
        for (int u = l; u <= r; u++) dp[i + 1][(j + u) % k] = 1;
      }
  cout << ans;
}
