#1150. COMMANDO - Phân đội

Một đơn vị quân đội có binh sỹ, đánh số từ đến . Để phù hợp với nhiệm vụ tác chiến của đơn vị, viên sỹ quan chỉ huy quyết định chia đơn vị thành từng phân đội.

Với mục đích đảm bảo hòa khí và giữ vững tinh thần đoàn kết nội bộ, mỗi phân đội sẽ bao gồm một số binh sỹ được đánh số liên tiếp nhau. Mỗi binh sỹ có một hiệu năng tác chiến, nếu là hiệu năng tác chiến cá nhân của binh sỹ , nguyên), thì hiệu năng tác chiến của phân đội bao gồm các binh sỹ từ đến sẽ là . Tuy nhiên kinh nghiệm chiến tranh cho thấy hiệu năng thực sự của phân đội được xác định bởi hàm , trong đó và là những hằng nguyên biết trước . Còn hiệu năng chung của toàn đơn vị thì bằng tổng hiệu năng của các phân đội. Rõ ràng rằng hiệu năng chung của đơn vị phụ thuộc vào cách xác định phân đội. Ví dụ, đơn vị có người với các hiệu năng cá nhân tương ứng là và với , thì việc chia thành phân đội và sẽ cho hiệu năng chung là . Đó là hiệu năng cao nhất có thể đạt được.

Yêu cầu: Cho . Hãy xác định hiệu năng chung lớn nhất có thể đạt được.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ;
• Dòng thứ hai chứa ba số nguyên và ;
• Dòng thứba3 chứa số nguyên .

Dữ liệu ra:

• Ghi ra một số nguyên là hiệu năng chung lớn nhất.

Ví dụ:

Dữ liệu vào:

4 
-1 1 -20 
2 2 3 4

Dữ liệu ra:

9

Giới hạn:

• Trong tất cả các test đều có: .
• số test có
• số test khác có