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 trong N viên bi có màu trắng hoặc màu đen, viên bi thứ i,(i=1,2,…,N) có khối lượng là A_i. Vinh sẽ lần lượt chọn các viên bi có thứ tự 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 phải thỏa 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 biết 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 cho trong file văn bản BAI5.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_1,A_2,…,A_N(1 ≤A_i≤M).

Dòng thứ ba ghi N số nguyên C_1,C_2,…,C_N mô tả màu 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 BAI5.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ụ:

Bai5.inp

4  7
1   2   4   5
0   0   1   1

Bai5.out

3