Cho một mảng \(A\) gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) cùng hai số nguyên \(K\) và \(C\).

Cần chia mảng \(A\) thành đúng \(K\) đoạn con liên tiếp không rỗng \(S_1, S_2, \dots, S_K\).
Chi phí của một đoạn con \(S = [A_l, A_{l+1}, \dots, A_r]\) được tính bằng:

Tổng chi phí của cách phân đoạn là tổng chi phí của \(K\) đoạn con đó. Hãy tìm cách chia mảng thành \(K\) đoạn sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, K, C\) (\(1 \le K \le N \le 10^5\), \(1 \le K \le 100\), \(0 \le C \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^4\)).

Output

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Example

4 2 5
2 3 1 4

60

Scoring

• Subtask 1 (100 điểm): \(1 \le K \le 100\), \(1 \le N \le 10^5\), \(0 \le C \le 10^9\), \(1 \le A_i \le 10^4\).