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:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(S (1 ≤ N ≤ 80, |S| ≤ 10^12 )\)

• Dòng thứ hai chứa \(N + 1\) số nguyên \(A_1, A_2,...,A_{N+1} (|A_i| ≤ 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 \(B_1, B_2,...,B_{N+1}(|B_i| ≤ 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 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\).

Sample Input

5    12
1  2  3  1  2  5
5  1  2  2  3  1

Sample Output

3