Du lịch

Sau bao năm chăm chỉ làm lụng và tiết kiệm, cuối cùng Sơn đã có đủ điều kiện để thực hiện được ước mơ của mình: đi du lịch ở nước ngoài.

Nơi Sơn đến là một quốc gia có $n$ địa điểm du lịch, được kết nối thành hình tròn. Các địa điểm được đánh số từ $1$ đến $n$, địa điểm $i$ có một con đường nối tới địa điểm $(imodn)+1$ với khoảng cách $d_i$. Quá yêu quý quốc gia này, Sơn quyết định sẽ ở đây $n$ ngày. Ngày thứ $i$, cậu sẽ thuê khách sạn ở địa điểm $i$, sau đó đi tham quan tất cả các địa điểm du lịch của quốc gia này và cuối ngày trở lại khách sạn. Nghĩa là trong ngày thứ $i$, Sơn đi đúng một vòng $i\to i+1\to \dots \to n\to 1\to \dots \to i$ theo chiều tăng của chỉ số.

Phương tiện di chuyển của cậu là một chiếc xe máy có dung tích bình xăng là $l$ lít xăng. Chiếc xe này tiêu thụ $1$ lít xăng mỗi kilomet. Ở mỗi địa điểm đều có một cây xăng, giá xăng ở địa điểm thứ $i$ là $c_i$ đồng/lít. Mỗi lần đổ xăng, Sơn có thể đổ một lượng tùy ý, miễn là lượng xăng trong bình không vượt quá $l$ lít.

Yêu cầu: Bạn hãy giúp Sơn tính xem, ngày thứ $i$, nếu cậu bắt đầu hành trình bằng một chiếc xe máy hết xăng, chi phí nhỏ nhất cậu cần bỏ ra để hoàn thành hành trình là bao nhiêu. Các ngày được tính độc lập với nhau: ngày nào xe cũng bắt đầu với bình hết xăng.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n,l$ là số địa điểm du lịch ở nơi cậu đến và dung tích bình xăng của Sơn $(3\le n\le 2·{10}^5$, $1\le l\le {10}^9)$.
• Dòng thứ hai chứa $n$ số nguyên dương $d_1,d_2,\dots ,d_n$, số thứ $i$ là khoảng cách từ địa điểm $i$ đến địa điểm $(imodn)+1$ $(1\le d_i\le l)$.
• Dòng thứ ba chứa $n$ số nguyên dương $c_1,c_2,\dots ,c_n$, số thứ $i$ là giá xăng ở địa điểm thứ $i$ $(1\le c_i\le 2)$.

Dữ liệu ra

Một dòng duy nhất chứa $n$ số nguyên, số nguyên thứ $i$ là chi phí Sơn cần bỏ ra trong ngày thứ $i$.

Ràng buộc

• $3\le n\le 2·{10}^5$, $1\le l\le {10}^9$.
• $1\le d_i\le l$.
• $1\le c_i\le 2$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n,l\le 100$.
• Subtask 2 ($40\%$ số điểm): $n\le 5000$.
• Subtask 3 ($30\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ