WAREHOUSE - Kho hàng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Một chiếc xe chuyên dụng cần lần lượt đi qua các trạm 1, 2,..., N để lấy hàng. Xe và các trạm này được bố trí cách đều nhau trên 1 đường thẳng. Xe nằm ở toạ độ 0. Trạm i nằm ở toạ độ i, có số lượng hàng là aiti là thời gian để xe bốc hết được toàn bộ lượng hàng ở trạm đó (i = 1, . . . , N). Xe có thể dừng và bốc hàng ở 1 số trạm x1 < x2 < · · · < xk nào đó. Khi dừng ở mỗi trạm xe sẽ bốc toàn bộ lượng hàng ở trạm đó. Vì lí do kỹ thuật nên khoảng cách giữa 2 trạm liên tiếp mà xe dừng xixi+1 không được phép vượt quá D đơn vị, đồng thời tổng thời gian bốc hàng tại các trạm không được vượt quá T.

Yêu cầu: Xác định các trạm dừng để bốc hàng thoả mãn các điều kiện đặt ra đồng thời tổng lượng hàng bốc được là lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa 3 số nguyên dương N, TD (1 ≤ N ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ D ≤ 10);
• Dòng thứ 2 chứa N số nguyên dương a1, . . . , aN (1 ≤ ai ≤ 10);
• Dòng thứ 3 chứa N số nguyên dường t1, . . . , tN (1 ≤ ti ≤ 10).

Kết quả Ghi ra một số nguyên là số dư trong phép chia lượng hàng bốc được cho 109 + 7.

Ví dụ

Input

6 6 2
6 8 5 10 11 6
1 2 2 3 3 2

Output

24

Giải thích: Xe sẽ dừng và bốc hàng tại các trạm 1, 2, 4 với tổng lượng hàng bốc được là 6 + 8 + 10 = 24


Nguồn: ĐPT '1819

Back to Top