#include <bits/stdc++.h>
using namespace std;
long long dp[505][505];
int main() {
  int n, k;
  long long sum = 0;
  int a, b;
  scanf("%d %d", &n, &k);
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &a, &b);
    for (int j = 0; j < k; j++) {
      if (dp[i - 1][j] >= 0) {
        int x = sum - dp[i - 1][j] * k - j;
        for (int s = 1; s < k && s <= a; s++) {
          if (b + s >= k) {
            int tmp1 = x + b - k + s;
            int tmp2 = j + a - s;
            dp[i][tmp2 % k] =
                max(dp[i][tmp2 % k], dp[i - 1][j] + 1 + tmp1 / k + tmp2 / k);
          }
        }
        dp[i][(j + a) % k] =
            max(dp[i][(j + a) % k], dp[i - 1][j] + (x + b) / k + (j + a) / k);
      }
    }
    sum = sum + a + b;
  }
  long long ans = 0;
  for (int i = 0; i < k; i++) {
    ans = max(ans, dp[n][i]);
  }
  cout << ans;
}
