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 \((i\ mod\ n)\ + \ 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à ngày cuối trở lại khách sạn.

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.

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.

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 \leq n \leq 2 \times 10^{5},\ 1 \leq l \leq 10^{9})\).

+ Dòng thứ hai chứa \(n\) số nguyên dương \(d_{1},\ d_{2},\ ...,\ d_{n}\), số thứ \(i\) là khoảng cách từ địa điểm \(i\) đến địa điểm \((i\ mod\ n)\ + \ 1\ (1 \leq d_{i} \leq l)\).

+ Dòng thứ ba chứa \(n\) số nguyên \(c_{1},\ c_{2},\ ...,\ c_{n}\), số thứ \(i\) là giá xăng ở địa điểm thứ \(i\ (1 \leq c_{i} \leq 2)\).

Kết quả:

+ 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\).

Ví dụ:

Giải thích:

Ở test ví dụ 1:

Nếu Sơn xuất phát ở địa điểm 1:

• Cậu đổ 1 lít xăng ở địa điểm 1 để đi sang địa điểm 2 và  tốn 2 đồng, trong bình còn 0 lít xăng.

• Cậu đổ 3 lít xăng ở địa điểm 2 để đi sang địa điểm 3 và  tốn 3 đồng, trong bình còn 0 lít xăng.

• Cậu đổ 2 lít xăng ở địa điểm 3 để đi sang địa điểm 4 và  tốn 2 đồng, trong bình còn 0 lít xăng.

• Cậu đổ 6 lít xăng ở địa điểm 4 để đi sang địa điểm 5 và  tốn 6 đồng, trong bình còn 1 lít xăng.

• Cậu đi từ địa điểm 5 sang địa điểm 1 mà  không cần đổ thêm xăng, trong bình còn 0 lít xăng. Vậy nếu xuất phát từ 1, Sơn sẽ tốn 2 + 3 + 2 + 6 = 13 đồng.

Ràng buộc:

+ Subtask 1 (30% điểm): \(n,\ l\ \leq \ 100\).

+ Subtask 2 (40% điểm): \(n\ \leq \ 5000\).

+ Subtask 3 (30% điểm): không có ràng buộc gì thêm.