Có một hình chữ nhật kích thước ~N * 1~ (cạnh trên và cạnh dưới độ dài ~N~, hai cạnh bên có độ dài là ~l~). 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. Một bạn muố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 gọi là thuộc hai hình thang).

Yêu cầu

Hãy cho biết 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~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~S~ ~(1 \le N \le 80, |S| \le 10^12)~
• Dòng thứ hai chứa ~N+1~ số nguyên ~A_1, A_2, ..., A_{N+1} (|A_i| \le 10^9~ với ~l \le i \le 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| \le 10^9~ với ~l \le i \le N)~ là các giá trị nguyên ghi ở cạnh dưới của hình chữ nhật.

Output

• 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ụ

Input

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

Output

3

Giải thích ví dụ

Cắt hai đường như sau để được 3 hình thang