Phi hành gia Tí đang thực hiện nhiệm vụ khám phá vũ trụ thì phi thuyền gặp sự cố cạn kiệt năng lượng. May mắn thay, Tí thu thập được một dãy gồm ~N~ tinh thể năng lượng xếp thành một hàng dọc, được đánh số thứ tự từ 1 đến ~N~. Tí cần sử dụng toàn bộ số tinh thể này để nạp đầy cho ~K~ lõi động cơ của phi thuyền. Quy trình nạp năng lượng phải tuân thủ nghiêm ngặt các điều kiện sau để tránh phát nổ:

• Mỗi lõi động cơ phải được nạp bằng một dãy các tinh thể liên tiếp nhau.

• Toàn bộ ~N~ tinh thể đều phải được phân bổ hết vào ~K~ lõi động cơ.

• Để tránh quá tải, mỗi lõi động cơ không được chứa nhiều hơn ~M~ tinh thể.

• Mỗi tinh thể mang một mức điện tích nhất định (có thể là điện tích âm hoặc dương). Công suất hoạt động của một lõi động cơ được tính bằng giá trị tuyệt đối của tổng điện tích các tinh thể bên trong lõi đó.

• Tổng công suất cung cấp cho phi thuyền bằng tổng công suất của tất cả ~K~ lõi động cơ.

Yêu cầu: Bạn có trong tay danh sách mức điện tích của các tinh thể. Hãy giúp phi hành gia Tí tính toán cách chia tinh thể sao cho tổng công suất cung cấp cho phi thuyền là lớn nhất để có thể khởi hành về Trái đất an toàn.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, K, M~ ~(1 \le N \le 3000, 1 \le M, K \le N)~.

• Dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(0 \le |A_i| \le 10^9, 1 \le i \le N)~ thể hiện mức điện tích của từng tinh thể.

Output

Tổng công suất lớn nhất có thể đạt được.

Scoring

Sample Input 1

5 2 4
-7 -7 17 3 -20

Sample Output 1

26

Sample Input 2

3 2 2
-6 -15 13

Sample Output 2

34

Notes

Ví dụ 1: Cách chia tinh thể để tạo ra công suất lớn nhất:

• Lõi 1: ~(-7, -7, 17, 3)~, có công suất là ~|-7 - 7 + 17 + 3| = 6~

• Lõi 2: ~(-20)~, có công suất là ~|-20| = 20~

Tổng: ~6 + 20 = 26~

Ví dụ 2: Chia làm 2 lõi: ~(-6, -15)~ và ~(13)~

Công suất là: ~|-6 - 15| + |13| = 34~