#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
long long dp[maxn][maxn];
int red[maxn], blue[maxn];
int n, k;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &red[i], &blue[i]);
  }
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  long long sum = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < k; ++j) {
      if (dp[i - 1][j] != -1) {
        int b = sum - dp[i - 1][j] * k - j;
        for (int r = max(1, k - blue[i]); r < k && r <= red[i]; ++r) {
          int b2 = b + blue[i] - (k - r);
          int r2 = j + red[i] - r;
          dp[i][r2 % k] =
              max(dp[i][r2 % k], dp[i - 1][j] + b2 / k + r2 / k + 1);
        }
        int b2 = b + blue[i];
        int r2 = j + red[i];
        dp[i][r2 % k] = max(dp[i][r2 % k], dp[i - 1][j] + b2 / k + r2 / k);
      }
    }
    sum += red[i] + blue[i];
  }
  long long ans = 0;
  for (int i = 0; i < k; ++i) ans = max(ans, dp[n][i]);
  printf("%I64d\n", ans);
}
