_
                  _ |_|_ 
                 (_|   |_)
                   |   |
                  _|_  |  _
                 (_| | | |_)
                   | | | |
                  _|_|_|_|_
                 |         |
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
          ~    ~    ~    ~    ~    ~

Khi đặt bút viết những dòng cuối cùng dâng lên Hoàng đế Carlos I, thuyền trưởng Juan Sebastián Elcano hồi tưởng lại quyết định sinh tử ở Nam Đại Tây Dương. Để trốn tránh các hạm đội tuần tra của Bồ Đào Nha, Elcano đã phải chọn lộ trình xuống các vĩ độ cực Nam hoang dã — nơi được mệnh danh là "Vĩ tuyến tử thần".
Lộ trình trên biển gồm \(N\) phân vùng hải lý nối tiếp nhau, đánh số từ \(1\) đến \(N\). Phân vùng \(i\) có chỉ số áp lực thời tiết và sóng biển tích lũy là \(A_i\) (\(A_i \ge 0\)).

Con tàu Victoria đã quá rệu rã, không thể di chuyển liên tục từ đầu đến cuối mà không bảo trì. Elcano có thể quyết định cho tàu thả neo đại tu tại các hòn đảo hoang bất kỳ lúc nào. Kế hoạch này là một canh bạc:

1. Chi phí neo đậu (\(C\)): Mỗi lần quyết định hạ neo đại tu quy mô lớn, hạm đội phải chấp nhận tốn một lượng tài nguyên cố định là \(C\) đơn vị (hao hụt lương thực, rủi ro bị phát hiện).

2. Áp lực tích lũy bình phương: Nếu tàu đi liên tục qua một chặng gồm các phân vùng từ \(l\) đến \(r\) mới dừng lại, áp lực phá hủy tác động lên vỏ gỗ tỷ lệ thuận với bình phương tổng chỉ số áp lực của chặng đó:

   \[\left(\sum_{i=l}^r A_i\right)^2\]

3. Giới hạn chịu tải tuyệt đối (\(L\)): Tại bất kỳ chặng di chuyển liên tục nào, tổng lực tác động không được vượt quá ngưỡng chịu đựng \(L\) của khung tàu (\(\sum_{i=l}^r A_i \le L\)). Nếu vượt quá, vỏ tàu sẽ nứt toác ngay lập tức.

Với tư cách là hoa tiêu vĩ đại nhất của chuyến viễn chinh, bạn hãy giúp Elcano tìm ra phương án chia chặng tối ưu sao cho tổng áp lực phá hủy của toàn bộ chuyến đi là nhỏ nhất.

Nhiệm vụ

• Cho mảng \(A\) gồm \(N\) số nguyên không âm và hai hằng số \(C, L\).
• Hãy chia mảng \(A\) thành một số mảng con liên tiếp (mỗi mảng con đại diện cho một chặng từ \(l\) đến \(r\)) sao cho:
  1. Mỗi mảng con đều thỏa mãn: \(\sum_{i=l}^r A_i \le L\).
  2. Tổng chi phí sau đây là nhỏ nhất:

Input

• Dòng thứ nhất chứa ba số nguyên \(N, C, L\) (\(1 \le N \le 10^5\), \(0 \le C \le 10^9\), \(0 \le L \le 10^9\))
• Dòng thứ hai chứa \(N\) số nguyên không âm \(A_1, A_2, \dots, A_N\) (\(0 \le A_i \le 10^4\))

Output

• In ra một số nguyên duy nhất là tổng chi phí tối thiểu tìm được. Nếu không có cách chia nào thỏa mãn điều kiện \(\sum A_i \le L\), in ra -1.

Example

5 10 8
3 4 2 5 2

108

3 10 5
2 7 1

-1

Scoring

• Subtask 1 (\(60\%\) số điểm): \(1 \le N \le 2000, 0 \le A_i \le 10^4, \, 0 \le C, L \le 10^9\)
• Subtask 2 (\(40\%\) số điểm): Không có ràng buộc nào thêm