1. const int NMAX = 505;

  2. int N, K, a[NMAX], b[NMAX];

  3. bool dp[NMAX][NMAX];


  5. int main()

  6. {

  7. #ifndef ONLINE_JUDGE

  8. ifstream cin("test.in");

  9. #endif

  10. #ifdef ONLINE_JUDGE

  11. ios_base::sync_with_stdio(false);

  12. cin.tie(nullptr);

  13. #endif

  14. long long sum = 0, answer = 0;

  15. cin >> N >> K;

  16. for (int i = 1; i <= N; ++i)

  17. {

  18. cin >> a[i] >> b[i];

  19. sum += a[i] + b[i];

  20. }

  21. dp[0][0] = true;

  22. for (int i = 1; i <= N; ++i)

  23. {

  24. for (int j = 0; j < K; ++j)

  25. {

  26. dp[i][j] = dp[i - 1][(j - a[i] % K + K) % K];

  27. for (int l = 0; l <= min(K - 1, a[i]); ++l)

  28. {

  29. if ((a[i] - l) % K + b[i] >= K)

  30. dp[i][j] |= dp[i - 1][(j - l + K) % K];

  31. }

  32. }

  33. }


  35. for (int i = 0; i < K; ++i)

  36. if (dp[N][i] == true)

  37. answer = max(answer, (sum - i) / K);

  38. cout << answer << "\n";



  40. return 0;

  41. }