Hôm nay là Ngày của Mẹ nên Tí quyết định chuẩn bị cho mẹ một bữa tối đặc biệt. Trên bàn bếp có một hàng gồm ~N~ nguyên liệu khác nhau đã được sơ chế và được đánh số theo thứ tự từ 1 đến ~N~. Tí cần sử dụng các nguyên liệu này để nấu ~K~ món ăn sao cho thoả mãn các điều kiện sau:

• Mỗi món ăn phải được làm từ một dãy các nguyên liệu liên tiếp.
• Tất cả các nguyên liệu đều phải được dùng để nấu ~K~ món ăn.
• Mỗi món ăn không được có nhiều hơn ~M~ nguyên liệu.

Mỗi món ăn có độ ngon được tính bằng giá trị tuyệt đối tổng giá trị dinh dưỡng của các nguyên liệu. Độ hài lòng của bữa tối được tính bằng tổng độ ngon của từng món ăn.

Bạn có được danh sách các nguyên liệu và giá trị dinh dưỡng của chúng, hãy tìm độ hài lòng lớn nhất của bữa tối.

Yêu cầu: Hãy tính độ hài lòng lớn nhất của bữa tối.

Input

• Dòng đầu ghi ba số ~N, K, M~ (~1 \le N \le 3000, 1 \le M, K \le N~).
• Dòng tiếp theo: giá trị dinh dưỡng của ~N~ nguyên liệu ~A_1, A_2, \dots, A_N~ (~0 \le |A_i| \le 10^9~ với ~1 \le i \le N~).

Output

• Ghi ra độ hài lòng lớn nhất của bữa tối.

Sample Input 1

5 2 4
-7 -7 17 3 -20

Sample Output 1

26