Bạn là chỉ huy của một đội quân gồm \(n\) người lính, được đánh số từ \(1\) đến \(n\). Để chuẩn bị cho trận đánh sắp tới, bạn muốn chia toàn bộ đội quân thành các đơn vị biệt kích. Nhằm tăng cường đoàn kết và tinh thần chiến đấu, mỗi đơn vị phải gồm một dãy liên tiếp các người lính, có dạng \((i,i+1,\ldots,i+k)\). Mỗi người lính thuộc đúng một đơn vị.

Người lính thứ \(i\) có sức chiến đấu \(x_i\). Sức chiến đấu ban đầu của một đơn vị là tổng sức chiến đấu của các thành viên:

Sau nhiều năm giành chiến thắng, bạn nhận thấy sức chiến đấu của một đơn vị cần được điều chỉnh theo công thức sau, trong đó \(a,b,c\) là các hệ số đã biết và \(a<0\):

Hãy chia đội quân thành các đơn vị sao cho tổng sức chiến đấu sau điều chỉnh của tất cả các đơn vị là lớn nhất.

Dữ liệu vào

Dữ liệu gồm ba dòng:

• Dòng đầu chứa số nguyên dương \(n\), số người lính.
• Dòng thứ hai chứa ba số nguyên \(a,b,c\), các hệ số của công thức điều chỉnh.
• Dòng cuối chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\) cách nhau bởi dấu cách, lần lượt là sức chiến đấu của các người lính từ \(1\) đến \(n\).

Dữ liệu ra

In một dòng chứa một số nguyên: tổng sức chiến đấu sau điều chỉnh lớn nhất có thể đạt được.

Ràng buộc

• \(1\le n\le 1\,000\,000\).
• \(-5\le a\le -1\).
• \(|b|\le 10\,000\,000\), \(|c|\le 10\,000\,000\).
• \(1\le x_i\le 100\) với mọi \(1\le i\le n\).

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

4
-1 10 -20
2 2 3 4

9

Nguồn

APIO 2010 — Commando, đề tiếng Anh phiên bản 1.2.