حتما می‌دونین که تیم امسال المپیاد کامپیوتر به دلیل قضیه انگشت‌نگاری و … به مسابقات جهانی اعزام نشدن. برای همین تصمیم گرفتن که یه جوری حال این آمریکایی‌های نامرد رو بگیرن! اولین پروژه مربوط به قطع برق می‌شد که همون‌جور که مطلع هستید با موفقیت انجام شد. بعد از اون پیشنهادات کلانی از سرتاسر دنیا(حتی خود آمریکا!) به باشگاه شد که همگی قصد خرابکاری و انتقام‌جویی از آمریکا رو داشتن! اما می‌دونین که اعضای تیم حسابی مشغول چرخوندن دوره‌ی تابستون و تصحیح برگه و … هستن. برای همین تصمیم گرفتن یکی از این پروژه‌ها که زیاد سخت نبود رو به شما بدن تا معلوم شه چی کاره‌این!

تعدادی برج هست که همشون روی یک خط قرار دارن. هر کدوم از این برج‌ها چند طبقه دارن. توی هر طبقه یه آدم کار می‌کنه که کشتنش یه مقدار مفیده(اگه بکشیش بهمون به همون اندازه پول میدن!) البته متاسفانه یه سری آدم خودی هم تو این برج‌ها هستن که اگه اونا را بکشیم یه مقدار ازمون پول می‌گیرن. یه سری هم هواپیما دارم (به میزان کافی!). قراره این هواپیماها رو بفرستیم که بخورن به این برج‌ها. هروقت یه هواپیما به یه طبق از یه برج می‌خوره همه‌ی طبقات بالای اون طبقه به اضافه‌ی خود اون طبقه نابود میشن! دقت کنید که به طبقات پایینی آسیبی نمیرسه. به برخی دلایل امنیتی موظف هستین تختریب رو طوری انجام بدین که در نهایت برجی نباشه که هم سمت راستش و هم سمت چپش برج بلندتر از اون داشته باشیم(هر برجی یا باید از همه‌ی سمت راستی‌هاش بلندتر مساوی باشه یا از همه‌ی سمت چپی‌هاش یا هر دو).

چیزی که بدیهیه اینه که شما می‌خواین بیش‌ترین سود رو ببرین. برنامه‌ای بنویسین که این کار رو بکنه.

در فایل ورودی در سطر اول تعداد برج‌ها اومده($n$) و بعد از اون $n$ سطر. طوری که سطر $i+1$ فایل ورودی بیانگر مشخصات $i$امین برج از سمت چپه. در این سطر در ابتدا عدد $a_i$ اومده که نشان‌دهنده‌‌ی تعداد طبقات برج $i$امه و سپس $a_i$ عدد اومده که نشون میدن به ترتیب از پایین برج تا بالا هر طبقه چقدر ارزش داره. $j+1$امین عدد از سطر نشان‌دهنده‌ی پولیه که از نابودی $j$امین طبقه به ما میرسه( و اگه منفی بود یعنی چقدر پول از دست می‌دیم).

نکته : حداکثر ۱۰۰۰ تا برج داریم و هر برج حداقل ۰ و حداکثر ۱۰۰۰ طبقه ارتفاع دارد و پول مربوط به هر طبقه از ۲۰۰۳ کم‌تر و از ۲۰۰۳- بیشتر است.

فایل خروجی باید $n+1$‌خط داشته باشه. تو خط اول بیش‌ترین سودی که میشه برد رو بنویسن و بعدش هم $n$ خط بنویسن که خط $i+1$ام از فایل خروجی میگه که $i$امین برج باید در پایان عملیات چند طبقه ارتفاع داشته باشه.

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

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