Dựng chung cư

Bên đường có \(n\) lô đất xếp thành hàng, lô thứ \(i\) chỉ cho phép xây cao tối đa \(r_i\) tầng. Chủ đầu tư muốn xây không quá \(k\) toà chung cư. Mỗi toà chiếm một đoạn gồm từ \(1\) đến \(t\) lô liên tiếp, và hai toà bất kỳ không được dùng chung lô nào (các đoạn không giao nhau). Có thể có lô bị bỏ trống.

Một toà chiếm các lô từ \(i\) đến \(j\) chỉ được cao bằng \(H = \min(r_i, r_{i+1}, \dots, r_j)\) tầng, và diện tích mặt tiền sử dụng được của nó là \(H \cdot (j - i + 1)\).

Hãy chọn các đoạn sao cho tổng diện tích mặt tiền của tất cả các toà là lớn nhất, và in ra giá trị đó.

Input

• Dòng đầu tiên gồm ba số nguyên \(n\), \(k\), \(t\).
• Dòng thứ hai gồm \(n\) số nguyên \(r_1, r_2, \dots, r_n\).

Output

In ra một số nguyên là tổng diện tích mặt tiền lớn nhất.

Constraints

• \(1 \le n \le 500\)
• \(1 \le k \le n\), \(1 \le t \le n\)
• \(0 \le r_i \le 100\)

Sample Input

9 2 3
5 9 4 8 2 7 7 3 10

Sample Output

26

Explanation

Chọn đoạn các lô \(2..4\) với độ cao \(\min(9,4,8)=4\), diện tích \(4 \cdot 3 = 12\), và đoạn \(6..7\) với độ cao \(7\), diện tích \(7 \cdot 2 = 14\). Tổng là \(26\).