Trò Chơi Quái Vật II

Bạn đang tiến qua $n$ màn chơi, mỗi màn có một con quái vật. Bạn phải tiêu diệt quái vật ở màn cuối cùng (màn $n$), nhưng có thể bỏ qua bất kỳ quái vật nào ở các màn $1$ đến $n-1$.

Ban đầu bạn có hệ số kỹ năng $x$. Khi tiêu diệt quái vật $i$ với hệ số kỹ năng hiện tại $f$, bạn mất $s_i·f$ thời gian và hệ số kỹ năng của bạn cập nhật thành $f_i$.

Hãy tìm tổng thời gian tối thiểu để hoàn thành tất cả các màn.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $x$.
• Dòng 2: $n$ số nguyên $s_1,s_2,\dots ,s_n$ — độ mạnh của các quái vật.
• Dòng 3: $n$ số nguyên $f_1,f_2,\dots ,f_n$ — hệ số kỹ năng sau khi tiêu diệt mỗi quái vật.

Dữ liệu ra

• Một số nguyên — tổng thời gian tối thiểu.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le x\le {10}^6$
• $1\le s_i,f_i\le {10}^6$

Ví dụ