Đề bài

Sau những cuộc phiêu lưu tại pháo đài Poenari, Vlad trở về nhà và, như một người Romania đích thực, việc đầu tiên anh nghĩ đến là cho ngựa ăn. Con ngựa không quá kén ăn nên Vlad dùng bãi cỏ làm nguồn thức ăn chính cho nó.

Vlad có một máy cắt cỏ với thùng chứa sức chứa \(c\). Anh chia bãi cỏ thành \(n\) luống, đánh số từ \(0\) đến \(n-1\), và phải cắt theo đúng thứ tự này. Luống \(i\) có \(v[i]\) đơn vị cỏ chưa cắt; Vlad mất \(a[i]\) giây để đẩy máy đi hết luống đó.

Sau khi đi qua một số luống, thùng chứa có thể đầy. Khi ấy máy ngừng cắt và để lại phần cỏ còn thừa trên luống đang đi qua. Mỗi lần như vậy, Vlad phải đổ thùng; thao tác này mất \(b\) giây và chỉ có thể thực hiện ở cuối một luống. Nếu thùng đầy khi Vlad đang đi qua luống \(i\), anh vẫn phải đẩy máy đến cuối luống, đổ thùng rồi đi qua luống đó thêm một lần nữa, hoặc nhiều lần nếu cần, để cắt hết phần cỏ còn lại.

Chẳng hạn, nếu cần đi qua luống \(i\) ba lần để cắt hết cỏ, thời gian là

Sau khi cắt xong toàn bộ bãi cỏ, Vlad bắt buộc phải đổ thùng chứa.

Vlad nhận ra đôi khi đổ thùng trước khi nó đầy có thể giúp tiết kiệm thời gian. Hãy tìm chiến lược giúp anh cắt xong toàn bộ bãi cỏ trong thời gian ít nhất.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

long long mow(
    int n,
    int c,
    int b,
    std::vector<int>& a,
    std::vector<int>& v
);

• n: số luống cỏ.
• c: sức chứa của thùng gom cỏ.
• b: số giây cần để đổ thùng.
• a: mảng độ dài \(n\); a[i] là thời gian đi hết luống \(i\).
• v: mảng độ dài \(n\); v[i] là lượng cỏ trên luống \(i\).
• Hàm phải trả về một số nguyên là thời gian nhỏ nhất để cắt xong bãi cỏ.
• Hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

• \(1\le n\le200\,000\).
• \(1\le a[i]\le10^9\) với mọi \(0\le i<n\).
• \(1\le v[i]\le10^9\) với mọi \(0\le i<n\).
• \(1\le b\le10^9\).
• \(1\le c\le10^9\).
• Kết quả đúng không vượt quá \(10^{18}\).

Phân nhóm

• Phân nhóm 1 (9 điểm): Tất cả các giá trị \(n,b,c,a[i],v[i]\) không vượt quá \(200\).
• Phân nhóm 2 (16 điểm): \(n,c\le5\,000\) và \(v[i]\le5\,000\) với mọi \(0\le i<n\).
• Phân nhóm 3 (36 điểm): \(c\le200\,000\).
• Phân nhóm 4 (17 điểm): \(a[0]=a[1]=\cdots=a[n-1]\).
• Phân nhóm 5 (22 điểm): Không có ràng buộc bổ sung.

Ví dụ

mow(3, 5, 2, {2, 10, 3}, {2, 4, 6})

24

mow(4, 10, 4, {1, 2, 1, 4}, {3, 2, 6, 7})

17

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n c b.
• Dòng \(2\): a[0] a[1] ... a[n-1].
• Dòng \(3\): v[0] v[1] ... v[n-1].

Trình chấm mẫu in kết quả của lời gọi mow với các tham số tương ứng.