Công ty đường sắt VNR vận hành một tuyến đường sắt duy nhất. Trên tuyến đường này có N nhà ga xếp thẳng hàng, được đánh số từ 1 đến N. Nhà ga i (1 ≤ i ≤ N-1) được nối với nhà ga i+1 bằng một đoạn đường sắt có chiều dài là 1.

Ở các nhà ga từ 2 đến N, mỗi nhà ga chứa một kiện hàng có giá trị tương ứng là A_i. VNR sở hữu một đoàn tàu hàng bắt đầu ở nhà ga 1 và có thể di chuyển qua lại trên tuyến đường sắt. Tại mỗi nhà ga, tàu có thể bốc dỡ hàng hóa lên tàu hoặc dỡ hàng xuống ga.

Nhiệm vụ của bạn là vận chuyển các kiện hàng từ nhà ga thứ 2 đến N về nhà ga 1. Biết rằng, đoàn tàu chỉ có thể chở tối đa W kiện hàng cùng một lúc và chỉ có thể di chuyển tối đa D đơn vị khoảng cách (tổng khoảng cách di chuyển trong cả hành trình). Vì vậy, có thể không thể vận chuyển được tất cả các kiện hàng về nhà ga 1.

Yêu cầu: Viết chương trình tính tổng giá trị lớn nhất của hàng hóa có thể vận chuyển về nhà ga 1 trong các điều kiện đã cho.

• Dòng đầu tiên: chứa 3 số nguyên dương N, W, D cách nhau bằng kí tự khoảng trắng.
• Dòng tiếp theo chứa N-1 số nguyên dương A_2, A_3,... A_n cách nhau bằng kí tự khoảng trắng là giá trị kiện hàng ở ga thứ i. (2 ≤i ≤N)

In ra tổng giá trị lớn nhất của hàng hóa có thể vận chuyển về nhà ga 1.

• 2 ≤ N ≤ 450.
• 1 ≤ W ≤ N-1.
• 2 ≤ D ≤ N^2 - N.
• 1 ≤ A_i ≤ 1,000,000 (2 ≤ i ≤ N).

Giải thích ví dụ 1:

• Có 4 nhà ga: 1, 2, 3, 4.
  • Nhà ga 2 chứa kiện hàng giá trị 1.
  • Nhà ga 3 chứa kiện hàng giá trị 1.
  • Nhà ga 4 chứa kiện hàng giá trị 1.

• Tàu bắt đầu tại ga 1, có thể chở tối đa 1 kiện hàng và di chuyển tối đa 10 đơn vị khoảng cách.

• Chiến lược:

  • Tàu từ ga 1 đến ga 2 (1 đơn vị khoảng cách).
  • Bốc kiện hàng giá trị 1 tại ga 2.
  • Quay lại ga 1 (1 đơn vị khoảng cách). Tổng khoảng cách đã di chuyển: 2.
  • Dỡ hàng tại ga 1.
  • Tàu từ ga 1 đến ga 4 (3 đơn vị khoảng cách).
  • Bốc kiện hàng giá trị 1 tại ga 4.
  • Quay lại ga 1 (3 đơn vị khoảng cách). Tổng khoảng cách đã di chuyển: 8.
  • Dỡ hàng tại ga 1.

• Tổng khoảng cách di chuyển là 8 (nhỏ hơn 10). Tổng giá trị hàng hóa tại ga 1 lúc này là 2.