#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 20;
int A[N], B[N], sum[N], vis[N][N];
long long dp[N][N];
int main() {
  int n, k;
  long long imax = -1;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &A[i], &B[i]);
    sum[i] = sum[i - 1] + A[i] + B[i];
  }
  vis[1][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < k; j++)
      if (vis[i][j]) {
        int u = sum[i - 1] - dp[i][j] * k - j;
        int a = j + A[i], b = u + B[i], c = a % k;
        dp[i + 1][c] = max(dp[i + 1][c], dp[i][j] + a / k + b / k);
        vis[i + 1][c] = 1;
        for (int h = 1; h < k; h++) {
          if (A[i] < h || B[i] < k - h) continue;
          int a = j + A[i] - h, b = u + B[i] - (k - h), c = a % k;
          dp[i + 1][c] = max(dp[i + 1][c], dp[i][j] + 1 + a / k + b / k);
          vis[i + 1][c] = 1;
        }
      }
  }
  for (int i = 0; i < k; i++) imax = max(imax, dp[n + 1][i]);
  cout << imax << endl;
  return 0;
}
