Con đường từ nhà đến trường có ~N~ bến xe. Ở mỗi bến xe đều bán ~N-1~ loại vé: nếu mua loại vé ~i~ ở bến xe thứ ~j~ thì có thể đến được các bến xe có chỉ số từ ~j-i~ đến ~j+i~ với chi phí ~P[i]~ (đồng). Mất ~M[i]~ (phút) để xuống xe và mua vé ở bến thứ ~i~ ~(2 \le i < N)~.

Gỉả sử thời gian di chuyển giữa các bến xe là không đáng kể, cần tính số tiền tối thiểu để đi từ bến ~1~ đến bến ~N~ nếu tổng số thời gian di chuyển không được phép vượt quá ~T~ phút ?

Input

• Dòng đầu tiên ghi hai số nguyên dương ~N~ và ~T~ ~(2 \le N \le 10^5, N - 1 \le T \le 10^9)~.
• Dòng thứ hai ghi ~N-1~ số nguyên ~P[i]~ - giá của loại vé thứ ~i = 1, 2, ..., N-1~ ~(1 \le P[i] \le 10^5)~.
• Dòng thứ ba ghi ~N-2~ số nguyên ~M[i]~ - số phút xuống và mua vé xe ở bến thứ ~i = 2, 3, ..., N-1~ ~(1 \le M[i] \le 10^5)~.

Output

• Chi phí tối thiểu nếu tổng số phút di chuyển không vượt quá ~T~.

Example

Input

4 4
1 2 3
1 4

Output

2