شما فرمانده یک گروهان شامل $n$ سرباز به شمارههای $1$ تا $n$ هستید. برای جنگی که در پیش است، شما طرح تقسیم این $n$ سرباز را به چند یگان کماندویی ریخته‌اید. به منظور گسترش وحدت و تقویت روحیه، هر واحد شامل دنباله‌ای پیوسته از سربازان به صورت $(i, i+1, \cdots , i+k)$ خواهد بود.

هر سرباز $i$ یک میزان تاثیر در جنگ برابر با $x_i$ دارد. در ابتدا میزان تاثیر در جنگ یک یگان کماندویی برابر با جمع میزان تاثیر در جنگ تک تک سربازانش بود. یعنی اگر میزان تاثیر در جنگ یک یگان کماندویی شامل سربازان $(i, i+1, \cdots , i+k)$ را برابر $x$ بگیریم، داریم: $x = x_i +x_{i+1} + \cdots + x_{i+k}$

با این حال، سال‌ها پیروزی شکوهمند شما را به این نتیجه رسانده که میزان تاثیر در جنگ یک یگان باید به این صورت محاسبه شود: $xꞌ$ که مقدار تعدیل شده میزان تاثیر در جنگ یک یگان است بوسیله معادله $xꞌ = ax^2+bx+c$ محاسبه می‌شود که در آن $a$, $b$, $c$ ضرایب معین ($a<0$) و $x$ مقدار ابتدایی میزان تاثیر یگان بوده است.

وظیفه شما به عنوان فرمانده این است که تقسیم سربازان خود به یگان های کماندویی را طوری انجام دهید که مجموع میزان تاثیر تعدیل شده تمام یگان‌ها بیشینه شود.

برای مثال فرض کنید شما $4$ سرباز دارید: $x_1 = 2, x_2 = 2, x_3 = 3, x_4 = 4$ و هم‌چنین ضرایب معادله تعدیل به این صورت است: $a = -1, b = 10, c = -20$ در این حالت به جواب تقسیم سربازان به سه یگان می باشد: سرباز $1$ و $2$ در یگان اول و سرباز $3$ در یگان دوم و سرباز $4$ در یگان سوم قرار می گیرند. میزان تاثیر ابتدایی یگان‌ها $4$، $3$ و $4$ خواهد بود و میزان تاثیر تعدیل شده بترتیب برابر $4$، $1$ و $4$ خواهد بود. مجموع میزان تاثیر تعدیل شده تمام یگان‌ها برابر با $9$ خواهد بود و از این بیشتر امکان‌پذیر نیست.

• ورودی شامل سه خط خواهد بود.
• خط اول شامل یک عدد صحیح مثبت $n$ تعداد سربازان است.
• در خط دوم $3$ عدد صحیح $a$، $b$ و $c$ که ضرایب معادله تعدیل هستند آمده است.
• در خط آخر $n$ عدد صحیح $x_1$ تا $x_n$ که با یک فاصه از هم جدا شده‌اند، آمده است که بترتیب بیانگر میزان تاثیر در جنگ سربازان $1$ تا $n$ می‌باشند.
• در ۲۰ درصد از تست‌ها $n \leq 1000$
• در ۵۰ درصد از تست‌ها $n \leq 10,000$
• در ۱۰۰ درصد از تست‌ها $n \leq 1,000,000$ و $-5 \leq a \leq -1$ و $|b| \leq 10,000,000 $ و $1 \leq x_i \leq 100$ و $|c| \leq 10,000,000$

تنها سطرِ خروجی یک عدد صحیح شامل بیشترین مجموع میزان تاثیر تعدیل شده دست یافتنی است.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل