Một trang trại trồng và cung cấp rau sạch ra thị trường cần lập kế hoạch sản xuất cho giai đoạn từ ngày 1 đến ngày \(n\) với tổng lượng hạt giống có để gieo trồng là \(Q\). Do đặc tính thời vụ, nên khi gieo trồng 1 đơn vị hạt giống vào ngày \(i\) thì sẽ thu được một sản lượng là \(a_i\).

Kế hoạch sản xuất sẽ bao gồm các đợt gieo trồng, mỗi đợt sẽ cần tính toán gieo trồng một lượng hạt giống là bao nhiêu và vào ngày nào. Do đặc tính sinh trưởng và thu hoạch của rau nên 2 đợt trồng liên tiếp cách nhau ít nhất \(K\) ngày: cụ thể nếu đợt thứ nhất bắt đầu gieo trồng vào ngày thứ \(i\) thì đợt gieo trồng tiếp theo sẽ chỉ có thể thực hiện từ ngày \(i + K\) trở đi. Ngoài ra, số đơn vị hạt giống gieo trồng trong mỗi đợt không vượt quá hằng số \(P\) cho trước.

Yêu cầu: Hãy tính toán kế hoạch sản xuất sao cho tổng sản lượng rau thu được là lớn nhất.

Dữ liệu vào

• Dòng 1: ghi 4 số nguyên dương \(n, K, Q và P (1 ≤ n ≤ 10^3, 1 ≤ K ≤ 10, 1 ≤ Q, P ≤ 10^3)\)

• Dòng thứ 2 ghi \(n\) số nguyên dương \(a_1, a_2 . . . , a_n(1 ≤ a_i ≤ 10^3)\).

Kết quả

• Tổng sản lượng lớn nhất thu được.

Sample Input

5 2 5 3
3 5 2 6 4

Sample Output

28