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à a_i và t_i 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 x₁ < x₂ < · · · < x_k 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 x_i và x_i+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, T và D (1 ≤ N ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ D ≤ 10);
• Dòng thứ 2 chứa N số nguyên dương a₁, . . . , a_N (1 ≤ a_i ≤ 10);
• Dòng thứ 3 chứa N số nguyên dường t₁, . . . , t_N (1 ≤ t_i ≤ 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 10⁹ + 7.