Xe Cổ

Có $n$ thành phố nằm trên một đường thẳng, đánh số từ trái sang phải là $c_1,c_2,\dots ,c_n$. Một chiếc xe muốn đi từ thành phố $c_1$ đến $c_n$.

Có $m=n-1$ đoạn đường một chiều: đoạn thứ $i$ nối $c_i$ với $c_{i+1}$ và dài $d_i$ km. Xe đi $1$ km mất $1$ giờ và tiêu tốn $1$ lít nhiên liệu.

Mỗi thành phố $c_i$ (với $1\le i\le m$, tức trừ thành phố cuối $c_n$) có một nguồn cung cấp $s_i$ lít nhiên liệu. Khi xe đi qua hoặc dừng lại ở thành phố $c_i$, toàn bộ lượng $s_i$ lít này lập tức được chuyển vào bình xăng. Sau đúng $k$ giờ kể từ lần chuyển đó, nguồn cung ở $c_i$ được nạp đầy lại, nên xe có thể dừng lại ở một thành phố để nạp nhiên liệu nhiều lần.

Ban đầu (tại thời điểm $0$) xe ở $c_1$ với bình xăng rỗng và ngay lập tức nhận $s_1$ lít từ $c_1$. Bình xăng có dung tích không giới hạn. Xe không thể tiếp tục di chuyển nếu bình xăng cạn kiệt khi đang ở giữa hai thành phố (nhiên liệu phải luôn đủ để đi hết mỗi đoạn đường).

Hãy tìm thời gian nhỏ nhất để xe đến được $c_n$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $m$ và $k$.
• Dòng thứ hai chứa $m$ số nguyên $d_1,d_2,\dots ,d_m$.
• Dòng thứ ba chứa $m$ số nguyên $s_1,s_2,\dots ,s_m$.

Dữ liệu ra

• In ra một số nguyên duy nhất: thời gian nhỏ nhất để xe đến được thành phố $c_n$.

Ràng buộc

• $1\le m,k\le 1000$
• $1\le d_i\le 1000$
• $1\le s_i\le 1000$

Ví dụ