Mỗi màu sắc có một hiệu ứng màu riêng được đại diện bởi một số nguyên nào đó.

Bờm hiện có một bức tranh với hiệu ứng màu ~0~. Cậu ta muốn tạo ra một bức tranh có hiệu ứng màu ~M~ nhưng hiện không có màu vẽ nên phải ra cửa hàng để mua.

Cửa hàng có bán ~N~ loại màu, màu thứ ~t~ có giá ~c[t]~ và sẽ giúp hiệu ứng màu của bức tranh tăng thêm một lượng ~a[t]~ một lần duy nhất.

Bạn hãy giúp Bờm mua màu vẽ sao cho cậu ta có thể tạo ra bức tranh với hiệu ứng màu như ý mà tốn ít tiền nhất.

Input

• Dòng 1: Hai số nguyên ~N, M~.
• Dòng 2: ~N~ số nguyên biểu diễn mảng ~a~.
• Dòng 3: ~N~ số nguyên biểu diễn mảng ~c~.

Output

• Một số nguyên duy nhất là số tiền Bờm cần chi ra ít nhất hoặc ~-1~ nếu không tồn tại cách mua để tô được hiệu ứng màu vừa ý Bờm.

Giới hạn

• ~40\%:~ ~1 \le N \le 20.~
• ~30\%:~ ~1 \le N \le 32, a[i], M \in [0, 10^6].~
• ~30\%:~ ~1 \le N \le 32.~
• Trong tất cả các test: ~|a[i]|, |M|, c[i]~ là các số nguyên thuộc ~[0, 10^9]~.

Example

Input

5 10
1 5 4 6 9
8 4 3 1 2

Output

4