Ban đầu Thuấn có một hình chữ nhật kích thước N  x  1 (cạnh trên và cạnh dưới độ dài N, hai cạnh bên có độ dài là 1).

            Cạnh trên và cạnh dưới, mỗi cạnh gồm N+1 điểm cách đều nhau tính từ đầu mút bên trái sang phải (gọi là các điểm có tọa độ nguyên) trên mỗi điểm này có ghi một giá trị nguyên.

            Thuấn chia hình chữ nhật ban đầu thành các hình thang bằng cách cắt các đường thẳng nối một điểm có tọa độ nguyên ở cạnh trên với một điểm có tọa độ nguyên ở cạnh dưới (các điểm nằm trên đường cắt được coi là thuộc hai hình thang).

Yêu cầu: Hãy cho biết Thuấn có thể tạo được ít nhất bao nhiêu hình thang thỏa mãn điều kiện: Tổng giá trị ghi trên các điểm có tọa độ nguyên thuộc mỗi hình thang không lớn hơn S.

Dữ liệu vào: Từ tệp test.inp có cấu trúc như sau:

-  Dòng đầu tiên chứa hai số nguyên N  và  S  (1 ≤ N ≤ 80, S≤ 1012 )

- Dòng thứ hai chứa N + 1 số nguyên  A1, A2,...,AN+1 (Ai≤ 10^9 với 1 ≤  i ≤ N là các giá trị nguyên ghi ở cạnh trên của hình chữ nhật). 

- Dòng thứ ba chứa N + 1 số nguyên  B1, B2,...,BN+1 (Bi≤ 10^9 với 1 ≤  i ≤ N là các giá trị nguyên ghi ở cạnh dưới của hình chữ nhật). 

Kết quả: Ghi vào tệp test.out gồm một số nguyên duy nhất là số hình thang ít nhất có thể tạo được, nếu không có cách chia thì ghi số -1.

Ví dụ:

Ràng buộc: Có 40% test có giá trị của N ≤ 20.