Từ xưa đến nay, ai cũng biết danh tiếng của tiến sĩ Hoàng Minh (hay còn đc người trong giới gọi là BLC) với hồ sơ cực khủng khiến Leonardo Da Vinci cũng phải nể phục. Anh ấy đã làm các loại nghề như: kĩ sư, giáo viên, thợ sửa ống nước, bác sĩ, nông dân cùng vô vàn những nghề khác. Hôm nay anh bắt đầu làm thêm một nghề nữa đó chính là bán áo quần. Vào ngày khai trương, anh ấy được một giám đốc tới tài trợ, vì muốn xem thử anh ấy thật sự giỏi như thế nào nên giám đốc đã cho anh ấy một bài toán có nội dung như sau:

Tiến sĩ có một danh sách \(n\) giá tiền của từng loại áo \(a[1], a[2], ..., a[n] \ (1 \le n \le 2 \times 10^5, \ -10^9 \le a[i] \le 10^9)\). Giám đốc cho tiến sĩ hai số \(k\) \((1 \le k \le min(20 , n))\) và \(x\) \((-10^9 \le x \le 10^9)\). Tiến sĩ có thể chọn ra \(k\) loại áo riêng biệt để cộng giá tiền của nó lên \(x\) đơn vị nhưng phải trừ đi \(x\) đơn vị các loại áo tiến sĩ không chọn. Sau khi chọn những loại áo nào cần tăng giá tiền thì tiến sĩ sẽ chọn một đoạn \(a[i], a[i + 1], ..., a[j] \space (1 \le i \le j \le n)\) để tính tổng các giá tiền trong đoạn đó, nó cũng chính là phần quà mà giám đốc muốn tặng cho tiến sĩ. Là một người tham lam, tiến sĩ muốn tìm cách làm sao để lấy được số tiền lớn nhất. Bạn hãy giúp tiến sĩ nhé.

Input

• Dòng thứ nhất nhập vào 3 số \(n, k, x\)
• Dòng thứ hai n số tương ứng giá tiền của từng loại áo quần \(a[1], a[2], ..., a[n]\)

Output

• Tổng giá tiền lớn nhất mà tiến sĩ nhận được

4 1 2
2 -1 2 3

5

Chọn a[4] để tăng lên x sau đó giảm các phần tử còn lại đi x thì dãy trở thành 0 -3 0 5.
Chọn đoạn i tới j là 4 tới 4 để có tổng lớn nhất là a[4] = 5.

Scoring

• Subtask 1 (\(20\%\) số điểm): \(1 \le k \le n \le 10\)
• Subtask 2 (\(30\%\) số điểm): \(1 \le k \le min(20, n), \space n \le 100\)
• Subtask 3 (\(50\%\) số điểm): Không có ràng buộc gì thêm