Tối đa số lần tách

Trong một buổi làm việc, FullHouse Dev được giao một nhiệm vụ thú vị từ đội ngũ Dữ liệu. Họ cần tìm cách tách một luồng dữ liệu sao cho số lượng số lẻ và số chẵn trong mỗi phần tách đều bằng nhau. Tuy nhiên, việc tách này phải tốn không quá \(K\) đồng. Đội ngũ đã bắt đầu phân tích và tìm ra giải pháp cho bài toán này.

Bài toán

FullHouse Dev nhận được một số nguyên \(N\), một mảng \(arr\) và một số nguyên \(K\). Nhiệm vụ của nhóm là xác định số lần tách tối đa có thể thực hiện trong mảng mà không vượt quá \(K\) đồng.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - kích thước của luồng dữ liệu.
• Dòng tiếp theo chứa số nguyên \(K\) - giới hạn chi phí.
• Dòng tiếp theo chứa \(N\) số nguyên - các phần tử của luồng dữ liệu.

OUTPUT FORMAT:

• In ra số lần tách tối đa có thể thực hiện trong mảng mà không vượt quá \(K\) đồng.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(0 \leq K \leq 10^9\)
• \(1 \leq arr[i] \leq 10^9\)

Ví dụ

INPUT

4
10
1 3 2 4

OUTPUT

0

Giải thích

• Trong ví dụ này, không thể thực hiện bất kỳ lần tách nào ngay cả khi có số tiền không giới hạn, vì điều kiện để tách hợp lệ không thể được thỏa mãn trong bất kỳ lần tách nào.