Vinh có N viên bi được xếp thành một hàng ngang, các viên bi được đánh số thứ tự từ 1 đến N (theo thứ tự từ trái sang phải). Mỗi viên bi có màu trắng hoặc màu đen, viên bi thứ i (i=1, 2, 3, …, N) có khối lượng A_i. Vinh sẽ lần lượt chọn các viên bi thứ i=1, 2, 3, …, N để xếp chúng vào các hộp. Các viên bi được xếp trong một hộp thoả mãn:

• Tổng khối lượng các viên bi không quá M.
• Các viên bi đều phải cùng màu.

Yêu cầu: Cho M, hãy tính xem, Vinh cần ít nhất bao nhiêu hộp để xếp hết N viên bi mà Vinh đang có.

Dữ liệu trong file văn bản Xepbi.inp gồm:

• Dòng thứ nhất ghi 2 số nguyên dương N và M.
• Dòng thứ hai ghi N số nguyên A₁, A₂, …, A_N (1<=A_i<=M)
• Dòng thứ ba ghi N số nguyên C₁, C₂, …, C_N mô tả màu của của N viên bi, nếu C_i=0 thì viên bi thứ i có màu trắng, nếu C_i=1 thì viên bi thứ i có màu đen.

Kết quả ghi ra file văn bản Xepbi.out gồm một số nguyên là số hộp ít nhất để Vinh có thể xếp hết N viên bi.

Ví dụ:

Giới hạn:

• A₁, A₂, …, A_N (1<=A_i<=10⁶);
• Có 50% số test ứng với N<=1000 và các viên bi có cùng màu;
• Có 50% số test ứng với N<=10⁶.