+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نوروز که به دلیل قرنطینه کم‌حوصله شده، می‌خواهد به سفری تفریحی برود. (او با استفاده از [اپلیکیشن بانکت](http://www.asredanesh.com/products-services/e-financial/e-banking/bankette/) بلیطی برای سفر تهیه کرده است). وی با استاد خود، آقا فیروز صحبت می‌کند که از او اجازه بگیرد تا بتواند در کلاس‌های آنلاینش شرکت نکند. از آن‌جایی که آقا فیروز به فکر سلامتی شاگردش است، می‌خواهد او را وادار کند تا در خانه بماند. برای این‌کار به او می‌گوید که در امتحان نمره $X$ گرفته است؛ ولی این شرایط برای بهبود نمره‌اش وجود دارد: + در صورتی که **به سفر نرود**، ۲۰ می‌گیرد. + اگر دقیقا **هفت روز** به سفر برود، همان نمره $X$ را می‌گیرد. + در غیر این صورت به ازای **هر یک روز، دقیقا یک نمره** کم می‌شود (اگر نمره او کم‌تر از صفر شود، همان نمره صفر را می‌گیرد). این حالت شامل حالت‌های که نوروز بین ۱ تا ۶ روز به سفر برود هم می‌شود. حال نوروز بلیط سفر خود را از بانکت خریده‌ و می‌داند که دقیقا $N$ روز به سفر می‌رود، اما به‌دلیل افسردگی از قرنطینه، نمره خود را حساب نمی‌کند. به او کمک کنید و بگویید چه نمره‌ای در این درس می‌گیرد. # ورودی در خط اول عدد صحیح $X$ آمده‌است که بیانگر نمره فعلی نوروز در درس بهداشت و سلامت می‌باشد. در خط دوم عدد صحیح $N$ آمده‌است که بیانگر تعداد روز‌هایی می‌باشد که نوروز می‌خواهد به سفر برود. $$ 0 \le X \le 20 $$ $$ 0 \le N \le 100$$ # خروجی در تنها خط خروجی، نمره نهایی‌ای که نوروز در درس بهداشت و سلامت می‌گیرد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 14 0 ``` ## خروجی نمونه ۱ ``` 20 ``` نمره اولیه نوروز ۱۴ است اما چون به مسافرت نمی‌رود، نمره ۲۰ را می‌گیرد. ## ورودی نمونه ۲ ``` 6 7 ``` ## خروجی نمونه ۲ ``` 6 ``` نمره اولیه نوروز ۶ است و به دلیل اینکه دقیقا ۷ روز به مسافرت می‌رود، همان نمره ۶ را می‌گیرد و نمره‌اش تغییری نمی‌کند. ## ورودی نمونه ۳ ``` 13 9 ``` ## خروجی نمونه ۳ ``` 4 ``` نمره اولیه نوروز ۱۳ است و به دلیل اینکه ۹ روز به مسافرت رفته، پس ۹ نمره از او کم می‌شود و نمره‌اش ۴ می‌شود.

بهداشت و سلامت

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

نوروز که به دلیل قرنطینه کم‌حوصله شده، می‌خواهد به سفری تفریحی برود. (او با استفاده از اپلیکیشن بانکت بلیطی برای سفر تهیه کرده است). وی با استاد خود، آقا فیروز صحبت می‌کند که از او اجازه بگیرد تا بتواند در کلاس‌های آنلاینش شرکت نکند.

از آن‌جایی که آقا فیروز به فکر سلامتی شاگردش است، می‌خواهد او را وادار کند تا در خانه بماند. برای این‌کار به او می‌گوید که در امتحان نمره $X$ گرفته است؛ ولی این شرایط برای بهبود نمره‌اش وجود دارد:

در صورتی که به سفر نرود، ۲۰ می‌گیرد.
اگر دقیقا هفت روز به سفر برود، همان نمره $X$ را می‌گیرد.
در غیر این صورت به ازای هر یک روز، دقیقا یک نمره کم می‌شود (اگر نمره او کم‌تر از صفر شود، همان نمره صفر را می‌گیرد). این حالت شامل حالت‌های که نوروز بین ۱ تا ۶ روز به سفر برود هم می‌شود.

حال نوروز بلیط سفر خود را از بانکت خریده‌ و می‌داند که دقیقا $N$ روز به سفر می‌رود، اما به‌دلیل افسردگی از قرنطینه، نمره خود را حساب نمی‌کند. به او کمک کنید و بگویید چه نمره‌ای در این درس می‌گیرد.

ورودی🔗

در خط اول عدد صحیح $X$ آمده‌است که بیانگر نمره فعلی نوروز در درس بهداشت و سلامت می‌باشد.

در خط دوم عدد صحیح $N$ آمده‌است که بیانگر تعداد روز‌هایی می‌باشد که نوروز می‌خواهد به سفر برود. $0 \le X \le 20$ $0 \le N \le 100$

خروجی🔗

در تنها خط خروجی، نمره نهایی‌ای که نوروز در درس بهداشت و سلامت می‌گیرد را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

14
0

خروجی نمونه ۱🔗

نمره اولیه نوروز ۱۴ است اما چون به مسافرت نمی‌رود، نمره ۲۰ را می‌گیرد.

ورودی نمونه ۲🔗

6
7

خروجی نمونه ۲🔗

نمره اولیه نوروز ۶ است و به دلیل اینکه دقیقا ۷ روز به مسافرت می‌رود، همان نمره ۶ را می‌گیرد و نمره‌اش تغییری نمی‌کند.

ورودی نمونه ۳🔗

13
9

خروجی نمونه ۳🔗

نمره اولیه نوروز ۱۳ است و به دلیل اینکه ۹ روز به مسافرت رفته، پس ۹ نمره از او کم می‌شود و نمره‌اش ۴ می‌شود.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از اینکه هر $k$ شاگرد آقا فیروز به‌خاطر او،‌ به مسافرت نرفتند؛ او برای اینکه آن‌ها را تشویق کند، تصمیم گرفت تا به همراه آن‌ها به قنادی کاف برود و برایشان کیک بخرد. پس از اینکه وارد قنادی شدند، آقا فیروز از دیدن قیمت کیک‌ها خیلی جا خورد ولی چون شاگردانش را خیلی دوست داشت، تصمیم گرفت حتما کیک را بخرد. او که معلم ریاضی بود با خود فکری کرد که هم شاگردان خوشحال باشند و هم خودش هزینه کم‌تری کند. در ویترین قنادی $n$ کیک کنار هم چیده شده که قیمت $i$امین آن‌ها $c_i$ است. آقا فیروز تصمیم گرفت تا کیک‌ها را به $k$ بازه **متوالی** تقسیم کند (هر کیک باید در دقیقا یک بازه باشد) و به شاگرد $i$ام بگوید بین کیک‌های بازه $i$ام یکی را که خوش‌مزه‌تر است انتخاب کند(هر کدام از شاگردان، کیکی را به عنوان خوش‌مزه‌ترین انتخاب می‌کند که از همه **گران‌تر** است و در صورتی که چند کیک با گران‌ترین قیمت وجود داشت، به دلخواه یکی از آن‌ها را انتخاب می‌کند). در نهایت او از بین $k$ کیکی که شاگردان انتخاب کردند، یکی از آن‌ها که در واقع **ارزان‌ترینشان** است را انتخاب می‌کند و برای آن‌ها می‌خرد. می‌دانیم در این ایام رعایت بهداشت ضروری است و به همین دلیل، آقا فیروز مشغول نصب [همراه‌بانک مهر ایران](http://www.asredanesh.com/products-services/e-financial/e-banking/gh-mehr-mobile-bank/) برای تلفن همراه خود است تا بتواند پول کیک را به صورت آنلاین و بدون رد و بدل کردن پول نقد پرداخت کند. در این فاصله شما باید شما راهکاری پیدا کنید که آقا فیروز کیک‌ها را دسته‌بندی کند که در نهایت کم‌ترین مقدار پول ممکن را کارت به کارت کند و این مقدار پول لازم را چاپ کنید. در واقع شما باید راهکاری برای دسته‌بندی کیک‌ها پیدا کنید که در آن کم‌ترین مقدار، میان بیشینه این دسته‌ها، کم‌ترین مقدار ممکن باشد و این مقدار را چاپ کنید. # ورودی در خط اول دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد کیک‌ها و تعداد شاگرد‌ها می‌باشند. در خط دوم $n$ عدد آمده‌ است که عدد $i$ام نمایانگر $c_i$ است. $$ 1 \le k \le n \le 5\ 000 $$ $$ 1 \le c_i \le 5\ 000$$ # خروجی در تنها خط خروجی، مقدار پولی که آقا فیروز می‌پردازد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 3 2 3 ``` ## خروجی نمونه ۱ ``` 3 ``` در این مثال هر گونه آقا فیروز کیک‌ها را بازه‌بندی کند، یک بازه به طول ۱ و یک بازه به طول ۲ ایجاد می‌شود که در هر دوی آن‌ها قیمت گران‌ترین کیک برابر ۳ است و بنابراین او راهی به جز پرداخت ۳ واحد پول ندارد. ## ورودی نمونه ۲ ``` 5 3 5 4 3 2 2 ``` ## خروجی نمونه ۲ ``` 2 ``` در این مثال آقا فیروز می‌تواند هر کدام از عناصر کناری را یک بازه و سه عنصر وسط را هم یک بازه در نظر بگیرد. در این صورت شاگردها کیک‌هایی با قیمت‌های ۵، ۴ و ۲ را پیشنهاد می‌دهند که او می‌تواند کیک با قیمت ۲ را بخرد و کمترین مقدار ممکن را پرداخت کرده است چون کیکی با قیمت کمتر وجود ندارد. ## ورودی نمونه ۳ ``` 4 1 1 3 4 2 ``` ## خروجی نمونه ۳ ``` 4 ``` در این مثال آقا فیروز تنها یک شاگرد دارد و مجبور است تمامی کیک‌ها را یک بازه در نظر بگیرد و در این صورت شاگردش نیز گران‌ترین کیک یعنی کیک با قیمت ۴ را انتخاب می‌کند.

کاف‌کیک

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

پس از اینکه هر $k$ شاگرد آقا فیروز به‌خاطر او،‌ به مسافرت نرفتند؛ او برای اینکه آن‌ها را تشویق کند، تصمیم گرفت تا به همراه آن‌ها به قنادی کاف برود و برایشان کیک بخرد.

پس از اینکه وارد قنادی شدند، آقا فیروز از دیدن قیمت کیک‌ها خیلی جا خورد ولی چون شاگردانش را خیلی دوست داشت، تصمیم گرفت حتما کیک را بخرد. او که معلم ریاضی بود با خود فکری کرد که هم شاگردان خوشحال باشند و هم خودش هزینه کم‌تری کند.

در ویترین قنادی $n$ کیک کنار هم چیده شده که قیمت $i$ امین آن‌ها $c_i$ است. آقا فیروز تصمیم گرفت تا کیک‌ها را به $k$ بازه متوالی تقسیم کند (هر کیک باید در دقیقا یک بازه باشد) و به شاگرد $i$ ام بگوید بین کیک‌های بازه $i$ ام یکی را که خوش‌مزه‌تر است انتخاب کند(هر کدام از شاگردان، کیکی را به عنوان خوش‌مزه‌ترین انتخاب می‌کند که از همه گران‌تر است و در صورتی که چند کیک با گران‌ترین قیمت وجود داشت، به دلخواه یکی از آن‌ها را انتخاب می‌کند).

در نهایت او از بین $k$ کیکی که شاگردان انتخاب کردند، یکی از آن‌ها که در واقع ارزان‌ترینشان است را انتخاب می‌کند و برای آن‌ها می‌خرد.

می‌دانیم در این ایام رعایت بهداشت ضروری است و به همین دلیل، آقا فیروز مشغول نصب همراه‌بانک مهر ایران برای تلفن همراه خود است تا بتواند پول کیک را به صورت آنلاین و بدون رد و بدل کردن پول نقد پرداخت کند.

در این فاصله شما باید شما راهکاری پیدا کنید که آقا فیروز کیک‌ها را دسته‌بندی کند که در نهایت کم‌ترین مقدار پول ممکن را کارت به کارت کند و این مقدار پول لازم را چاپ کنید.

در واقع شما باید راهکاری برای دسته‌بندی کیک‌ها پیدا کنید که در آن کم‌ترین مقدار، میان بیشینه این دسته‌ها، کم‌ترین مقدار ممکن باشد و این مقدار را چاپ کنید.

ورودی🔗

در خط اول دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد کیک‌ها و تعداد شاگرد‌ها می‌باشند.

در خط دوم $n$ عدد آمده‌ است که عدد $i$ ام نمایانگر $c_i$ است. $1 \le k \le n \le 5\ 000$ $1 \le c_i \le 5\ 000$

خروجی🔗

در تنها خط خروجی، مقدار پولی که آقا فیروز می‌پردازد را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3 2
3 2 3

خروجی نمونه ۱🔗

در این مثال هر گونه آقا فیروز کیک‌ها را بازه‌بندی کند، یک بازه به طول ۱ و یک بازه به طول ۲ ایجاد می‌شود که در هر دوی آن‌ها قیمت گران‌ترین کیک برابر ۳ است و بنابراین او راهی به جز پرداخت ۳ واحد پول ندارد.

ورودی نمونه ۲🔗

5 3
5 4 3 2 2

خروجی نمونه ۲🔗

در این مثال آقا فیروز می‌تواند هر کدام از عناصر کناری را یک بازه و سه عنصر وسط را هم یک بازه در نظر بگیرد. در این صورت شاگردها کیک‌هایی با قیمت‌های ۵، ۴ و ۲ را پیشنهاد می‌دهند که او می‌تواند کیک با قیمت ۲ را بخرد و کمترین مقدار ممکن را پرداخت کرده است چون کیکی با قیمت کمتر وجود ندارد.

ورودی نمونه ۳🔗

4 1
1 3 4 2

خروجی نمونه ۳🔗

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز به تازگی کارهای مدیریت ساختمان خود را با استفاده از [نرم‌افزار سبزپرداز](https://sabzpardaz.org/) انجام می‌دهد؛ این نرم‌افزار به او کمک می‌کند تا کارهایش را خیلی سریع‌تر انجام دهد و وقت بیشتری برای بازی با نوروز داشته باشد. به همین منظور او یک جدول $n \times m$ بر روی زمین کشید و در هر کدام از خانه‌های آن، تعدادی کشمش قرار داد. البته در بعضی از خانه‌های جدول چمن قرار داشت و در آن‌ها کشمش نگذاشت (سطرهای جدول از بالا به پایین از ۱ تا $n$ و ستون‌ها از چپ به راست با ۱ تا $m$ شماره‌گذاری شده‌اند). حال نوبت نوروز است که بازی کند. او ابتدا باید **یکی از خانه‌های سطر پایین جدول** (سطر شماره $n$) را انتخاب کند و بر روی آن برود. سپس طبق گفته آقا فیروز هر بار می‌تواند یکی از دو حرکت زیر را انجام دهد (به شرطی که به خانه‌ای که چمن دارد و یا خارج از جدول است نرود): + یک خانه به چپ برود. + یک حرکت شبیه اسب شطرنج داشته باشد؛ یعنی ابتدا دو سطر به بالا برود و سپس اگر تاکنون زوج بار از این حرکت استفاده کرده بود، یک خانه به سمت چپ و در غیر این صورت یک خانه به سمت راست برود. (توجه کنید که صرفا باید خانه آخر چمن نداشته باشد و اگر خانه دو سطر بالاتر چمن داشته باشد، مشکلی در حرکت به وجود نمی‌آورد) هم‌چنین نوروز زمانی می‌تواند به بازی خاتمه دهد که در **سطر شماره یک** باشد. از آن‌جایی که نوروز خیلی کشمش دوست دارد، هر زمان که وارد یک خانه می‌شود، همه کشمش‌های آن را برای خودش برمی‌دارد. حال او از شما می‌خواهد تا بگویید با شرایط بالا حداکثر چند کشمش می‌تواند به دست آورد. هم‌چنین اگر مسیری با شرایط بالا وجود نداشته باشد، نوروز نمی‌تواند هیچ کشمشی به دست بیاورد و باید صفر چاپ کنید. # ورودی در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب طول و عرض جدول بازی را نشان می‌دهند. تضمین می‌شود که $n$ عددی فرد است. در $i$امین خط از $n$ خط بعدی $m$ عدد آمده است که $j$امین آن‌ها نشان‌دهنده تعداد کشمش‌های خانه واقع در تقاطع سطر $i$ام و ستون $j$ام می‌باشد. این تعداد را با $a_{i, j}$ نشان می‌دهیم. $$ 1 \le n, m \le 1\ 000$$ $$ 0 \le a_{i, j} \le 100\ 000$$ اگر تعداد کشمش‌های واقع در یک خانه صفر باشد، یعنی آن خانه دارای چمن است و نوروز نمی‌تواند بر روی آن برود. # خروجی در تنها خط خروجی، حداکثر تعداد کشمش‌هایی که نوروز می‌تواند بخورد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 5 0 4 2 0 5 ``` ## خروجی نمونه ۱ ``` 6 ``` نوروز می‌تواند از خانه سوم تنها سطر بازی شروع کرده و سپس یک خانه به چپ بیاید و در همان‌جا کار خود را تمام کند که در این صورت ۶ کشمش نصیب او می‌شود. ## ورودی نمونه ۲ ``` 3 4 7 0 6 10 1 8 3 6 7 0 6 10 ``` ## خروجی نمونه ۲ ``` 16 ``` در این‌جا نوروز می‌تواند از خانه چهارم سطر سوم شروع کند و سپس با یک حرکت به خانه سوم سطر اول بیاید و دیگر هم نمی‌تواند حرکتی بکند. در این صورت او ۱۶ کشمش به‌دست می‌آورد که با کمی بررسی معلوم می‌شود این مقدار ماکسیمم است.

کشمش در پارک

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

آقا فیروز به تازگی کارهای مدیریت ساختمان خود را با استفاده از نرم‌افزار سبزپرداز انجام می‌دهد؛ این نرم‌افزار به او کمک می‌کند تا کارهایش را خیلی سریع‌تر انجام دهد و وقت بیشتری برای بازی با نوروز داشته باشد.

به همین منظور او یک جدول $n \times m$ بر روی زمین کشید و در هر کدام از خانه‌های آن، تعدادی کشمش قرار داد. البته در بعضی از خانه‌های جدول چمن قرار داشت و در آن‌ها کشمش نگذاشت (سطرهای جدول از بالا به پایین از ۱ تا $n$ و ستون‌ها از چپ به راست با ۱ تا $m$ شماره‌گذاری شده‌اند).

حال نوبت نوروز است که بازی کند. او ابتدا باید یکی از خانه‌های سطر پایین جدول (سطر شماره $n$ ) را انتخاب کند و بر روی آن برود. سپس طبق گفته آقا فیروز هر بار می‌تواند یکی از دو حرکت زیر را انجام دهد (به شرطی که به خانه‌ای که چمن دارد و یا خارج از جدول است نرود):

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

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

از آن‌جایی که نوروز خیلی کشمش دوست دارد، هر زمان که وارد یک خانه می‌شود، همه کشمش‌های آن را برای خودش برمی‌دارد. حال او از شما می‌خواهد تا بگویید با شرایط بالا حداکثر چند کشمش می‌تواند به دست آورد. هم‌چنین اگر مسیری با شرایط بالا وجود نداشته باشد، نوروز نمی‌تواند هیچ کشمشی به دست بیاورد و باید صفر چاپ کنید.

ورودی🔗

در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب طول و عرض جدول بازی را نشان می‌دهند. تضمین می‌شود که $n$ عددی فرد است.

در $i$ امین خط از $n$ خط بعدی $m$ عدد آمده است که $j$ امین آن‌ها نشان‌دهنده تعداد کشمش‌های خانه واقع در تقاطع سطر $i$ ام و ستون $j$ ام می‌باشد. این تعداد را با $a_{i, j}$ نشان می‌دهیم. $1 \le n, m \le 1\ 000$ $0 \le a_{i, j} \le 100\ 000$ اگر تعداد کشمش‌های واقع در یک خانه صفر باشد، یعنی آن خانه دارای چمن است و نوروز نمی‌تواند بر روی آن برود.

خروجی🔗

در تنها خط خروجی، حداکثر تعداد کشمش‌هایی که نوروز می‌تواند بخورد را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1 5
0 4 2 0 5

خروجی نمونه ۱🔗

نوروز می‌تواند از خانه سوم تنها سطر بازی شروع کرده و سپس یک خانه به چپ بیاید و در همان‌جا کار خود را تمام کند که در این صورت ۶ کشمش نصیب او می‌شود.

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

در این‌جا نوروز می‌تواند از خانه چهارم سطر سوم شروع کند و سپس با یک حرکت به خانه سوم سطر اول بیاید و دیگر هم نمی‌تواند حرکتی بکند. در این صورت او ۱۶ کشمش به‌دست می‌آورد که با کمی بررسی معلوم می‌شود این مقدار ماکسیمم است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که به‌دلیل قیمت بالای کیک، به تنگ آمده بود، تصمیم گرفت تا در شرکت تاکسیرانی تپ‌نپ کار کند. شهری که آقا فیروز در آن زندگی‌ می‌کند شامل $n$ میدان است که در یک خط راست قرار دارند و به ترتیب از چپ به راست با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند و در وسط میدان شماره $i$، مجسمه‌ای با ارتفاع $h_i$ متر وجود دارد. هر مسافر در برنامه تپ‌نپ درخواستی به صورت $(i, j)$ می‌دهد و به این معنی است که می‌خواهد از میدان $i$ به میدان $j$ که $j < i$ است، برود. متاسفانه برنامه‌ی مسیریاب آقا فیروز خراب شده‌ و مسافرین باید به او آدرس بدهند. مسافر در هر مرحله یک عدد $k$ به آقا فیروز می‌گوید و او به سمت چپ حرکت می‌کند تا به **اولین** میدانی برسد که ارتفاع مجسمه‌اش دقیقا $k$ متر باشد. مسافر طوری عدد را می‌گوید که چنین میدانی در سمت چپ میدان فعلی و قبل از میدان $j - 1$ وجود داشته باشد. در نهایت وقتی مسافر به مقصد رسید، آقا فیروز به تعداد عددهایی که مسافر به او گفته‌‌، از او پول می‌گیرد و می‌دانیم مسافر‌ها به گونه‌ای آدرس می‌دهند که **کمترین پول** را به آقا فیروز بدهند. هم‌چنین آقا فیروز تا زمانی که یک مسافر را به مقصد نرسانده، او را پیاده نمی‌کند و در هر زمان **دقیقا یک مسافر** می‌تواند سوار ماشین شود. آقا فیروز که به پول نیاز دارد، می‌خواهد ببیند اگر به ازای هر $i$ و $j$ که $j < i$ است، درخواست $(i, j)$ را قبول کند، در مجموع چقدر پول بدست می‌آورد؛ اما بدلیل اینکه رانندگی انرژی زیادی از وی می‌گیرد، او از شما درخواست کرده‌ تا شما برایش این مقدار را حساب کنید. از آنجایی که ممکن است خروجی عددی بزرگ شود، جواب نهایی را به باقیمانده $10^9 + 7$ خروجی دهید. # ورودی در خط اول ورودی عدد $n$ می‌آید که بیانگر تعداد میدان‌های شهر است. در خط دوم به ترتیب $n$ عدد $h_1, h_2, h_3, \dots, h_n\ $ می‌آیند که $h_i$ برابر با ارتفاع مجسمه‌ای است که در میدان $i$ام قرار دارد. $$ 1 \le n \le 100\ 000 $$ $$ 1 \le h_i \le 100\ 000$$ # خروجی در تنها خط خروجی، مجموع پولی که آقا فیروز می‌تواند کسب کند را بگوید. # مثال ## ورودی نمونه ۱ ``` 3 4 1 2 ``` ## خروجی نمونه ۱ ``` 3 ``` درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است: + (۲, ۱) = ۱ + (۳, ۱) = ۱ + (۳, ۲) = ۱ ## ورودی نمونه ۲ ``` 5 3 3 3 1 2 ``` ## خروجی نمونه ۲ ``` 17 ``` درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است: + (۲, ۱) = ۱ + (۳, ۱) = ۲ + (۴, ۱) = ۳ + (۵, ۱) = ۳ + (۳, ۲) = ۱ + (۴, ۲) = ۲ + (۵, ۲) = ۲ + (۴, ۳) = ۱ + (۵, ۳) = ۱ + (۵, ۴) = ۱

عاشق سرعت

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

آقا فیروز که به‌دلیل قیمت بالای کیک، به تنگ آمده بود، تصمیم گرفت تا در شرکت تاکسیرانی تپ‌نپ کار کند. شهری که آقا فیروز در آن زندگی‌ می‌کند شامل $n$ میدان است که در یک خط راست قرار دارند و به ترتیب از چپ به راست با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند و در وسط میدان شماره $i$ ، مجسمه‌ای با ارتفاع $h_i$ متر وجود دارد.

هر مسافر در برنامه تپ‌نپ درخواستی به صورت $(i, j)$ می‌دهد و به این معنی است که می‌خواهد از میدان $i$ به میدان $j$ که $j < i$ است، برود.

متاسفانه برنامه‌ی مسیریاب آقا فیروز خراب شده‌ و مسافرین باید به او آدرس بدهند. مسافر در هر مرحله یک عدد $k$ به آقا فیروز می‌گوید و او به سمت چپ حرکت می‌کند تا به اولین میدانی برسد که ارتفاع مجسمه‌اش دقیقا $k$ متر باشد. مسافر طوری عدد را می‌گوید که چنین میدانی در سمت چپ میدان فعلی و قبل از میدان $j - 1$ وجود داشته باشد.

در نهایت وقتی مسافر به مقصد رسید، آقا فیروز به تعداد عددهایی که مسافر به او گفته‌‌، از او پول می‌گیرد و می‌دانیم مسافر‌ها به گونه‌ای آدرس می‌دهند که کمترین پول را به آقا فیروز بدهند.

هم‌چنین آقا فیروز تا زمانی که یک مسافر را به مقصد نرسانده، او را پیاده نمی‌کند و در هر زمان دقیقا یک مسافر می‌تواند سوار ماشین شود.

آقا فیروز که به پول نیاز دارد، می‌خواهد ببیند اگر به ازای هر $i$ و $j$ که $j < i$ است، درخواست $(i, j)$ را قبول کند، در مجموع چقدر پول بدست می‌آورد؛ اما بدلیل اینکه رانندگی انرژی زیادی از وی می‌گیرد، او از شما درخواست کرده‌ تا شما برایش این مقدار را حساب کنید.

از آنجایی که ممکن است خروجی عددی بزرگ شود، جواب نهایی را به باقیمانده $10^9 + 7$ خروجی دهید.

ورودی🔗

در خط اول ورودی عدد $n$ می‌آید که بیانگر تعداد میدان‌های شهر است.

در خط دوم به ترتیب $n$ عدد $h_1, h_2, h_3, \dots, h_n\$ می‌آیند که $h_i$ برابر با ارتفاع مجسمه‌ای است که در میدان $i$ ام قرار دارد. $1 \le n \le 100\ 000$ $1 \le h_i \le 100\ 000$

خروجی🔗

در تنها خط خروجی، مجموع پولی که آقا فیروز می‌تواند کسب کند را بگوید.

مثال🔗

ورودی نمونه ۱🔗

3
4 1 2

خروجی نمونه ۱🔗

درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است:

(۲, ۱) = ۱
(۳, ۱) = ۱
(۳, ۲) = ۱

ورودی نمونه ۲🔗

5
3 3 3 1 2

خروجی نمونه ۲🔗

درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است:

(۲, ۱) = ۱
(۳, ۱) = ۲
(۴, ۱) = ۳
(۵, ۱) = ۳
(۳, ۲) = ۱
(۴, ۲) = ۲
(۵, ۲) = ۲
(۴, ۳) = ۱
(۵, ۳) = ۱
(۵, ۴) = ۱

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گرچه آقا فیروز در تپ‌نپ خیلی اذیت شد ولی توانست پول خوبی به دست آورد. او تصمیم گرفت با این پول یک بازی فکری برای بچه‌هایش بخرد تا هوش ریاضی آن‌ها را پرورش دهد. وقتی آقا فیروز بازی را به پسرش علی داد، او خیلی خوشحال شد و سریع شروع به بازی کرد. بازی از یک صفحه تشکیل شده بود که روی آن دو عدد $n$ و $m$ نوشته شده بود و در زیر آن $n$ نقطه کشیده شده بود که $m$ جفت از آن‌ها با پاره‌خط‌هایی به‌صورت خط‌چین به هم وصل شده بودند. علی باید طوری پاره‌خط‌ها را با رنگ‌های ۱ و ۲ و ۳ رنگ‌آمیزی می‌کرد که در انتها هر پاره‌خطی که رنگ ۱ دارد، حتما حداقل یک پاره‌خط مجاور با رنگ ۲ داشته باشد. دو پاره‌خط مجاور هستند اگر یک سر آن‌ها مشترک باشد. علی که از راحتی این بازی جا خورده بود، تصمیم گرفت تا هوش ریاضی خود را به پدرش ثابت کند و تعداد روش‌های رنگ‌آمیزی صفحه با شرایط را به دست آورد. او که در ابتدا متوجه سختی مسئله نبود، پس از مدتی فکر کردن و ناتوانی در حل آن خیلی ناراحت شد. حال برای این که علی ناراحت نشود شما تعداد روش‌‌های رنگ‌آمیزی را به دست آورید و به او بگویید. همچنین به‌دلیل اینکه ممکن است خروجی بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ چاپ کنید. # ورودی در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب تعداد نقاط و پاره‌خط‌ها را نشان می‌دهد. در $i$امین خط از $m$ خط بعدی دو عدد $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ وجود پاره‌خطی بین دو نقطه با شماره $v_i$ و $u_i$ می‌باشد. تضمین می‌شود همواره $v_i$ و $u_i$ متفاوت هستند و بین هر جفتی حداکثر یک پاره‌خط‌ قرار دارد. $$1 \le n \le 18$$ $$1 \le m \le \frac{n \times (n - 1)}{2}$$ $$1 \le v_i, u_i \le n$$ # خروجی در تنها خط خروجی، تعداد روش‌های رنگ‌آمیزی پاره‌خط‌ها را به باقیمانده $10^9 + 7$ به دست آورید به‌طوری که شرایط بازی رعایت شود. # مثال ## ورودی نمونه ۱ ``` 4 2 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 3 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` 20 ```

بازی فکری

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

گرچه آقا فیروز در تپ‌نپ خیلی اذیت شد ولی توانست پول خوبی به دست آورد. او تصمیم گرفت با این پول یک بازی فکری برای بچه‌هایش بخرد تا هوش ریاضی آن‌ها را پرورش دهد.

وقتی آقا فیروز بازی را به پسرش علی داد، او خیلی خوشحال شد و سریع شروع به بازی کرد. بازی از یک صفحه تشکیل شده بود که روی آن دو عدد $n$ و $m$ نوشته شده بود و در زیر آن $n$ نقطه کشیده شده بود که $m$ جفت از آن‌ها با پاره‌خط‌هایی به‌صورت خط‌چین به هم وصل شده بودند.

علی باید طوری پاره‌خط‌ها را با رنگ‌های ۱ و ۲ و ۳ رنگ‌آمیزی می‌کرد که در انتها هر پاره‌خطی که رنگ ۱ دارد، حتما حداقل یک پاره‌خط مجاور با رنگ ۲ داشته باشد. دو پاره‌خط مجاور هستند اگر یک سر آن‌ها مشترک باشد.

علی که از راحتی این بازی جا خورده بود، تصمیم گرفت تا هوش ریاضی خود را به پدرش ثابت کند و تعداد روش‌های رنگ‌آمیزی صفحه با شرایط را به دست آورد. او که در ابتدا متوجه سختی مسئله نبود، پس از مدتی فکر کردن و ناتوانی در حل آن خیلی ناراحت شد.

حال برای این که علی ناراحت نشود شما تعداد روش‌‌های رنگ‌آمیزی را به دست آورید و به او بگویید.

همچنین به‌دلیل اینکه ممکن است خروجی بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ چاپ کنید.

ورودی🔗

در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب تعداد نقاط و پاره‌خط‌ها را نشان می‌دهد.

در $i$ امین خط از $m$ خط بعدی دو عدد $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ وجود پاره‌خطی بین دو نقطه با شماره $v_i$ و $u_i$ می‌باشد. تضمین می‌شود همواره $v_i$ و $u_i$ متفاوت هستند و بین هر جفتی حداکثر یک پاره‌خط‌ قرار دارد. $1 \le n \le 18$ $1 \le m \le \frac{n \times (n - 1)}{2}$ $1 \le v_i, u_i \le n$

خروجی🔗

در تنها خط خروجی، تعداد روش‌های رنگ‌آمیزی پاره‌خط‌ها را به باقیمانده $10^9 + 7$ به دست آورید به‌طوری که شرایط بازی رعایت شود.

مثال🔗

ورودی نمونه ۱🔗

4 2
1 2
3 4

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که در طی ماه‌های اخیر عملکرد خیره‌کننده‌ای در کار و نظارتش بر دیگران داشت، توسط شرکت عمرانی سرداد به استخدام درآمد. شرکت عصر دانش‌افزار که در زمینه طراحی و ساخت اپلیکیشن‌های بانکی، مالی و خدمات پرداخت فعالیت دارد، کارهای نرم‌افزاری این شرکت عمرانی را انجام می‌دهد. در پروژه‌ای که به آقا فیروز داده‌ شده، $n$ روستا وجود دارد که از $1$ تا $n$ شماره‌گذاری شده‌اند. همچنین یک لیست شامل $n - 1$ جاده به آقا فیروز داده‌ شده که هر جاده دوتا از روستاها را به هم وصل می‌کند. تضمین می‌شود پس از احداث جاده‌ها می‌توان با پیمایش تعدادی جاده از هر روستایی به هر روستای دیگری رفت. همچنین در هر روستا، یک سوله وجود دارد که درون سوله واقع در روستای شماره $i$، دقیقا $i$ تن خاک وجود دارد. همچنین می‌دانیم برای احداث جاده‌ای بین دو روستای $u$ و $v$، باید **دقیقا از یکی از این دو روستا، دقیقا ۱ تن خاک** برداشت. حال آقا فیروز که تازه استخدام شده‌، می‌خواهد خودی نشان دهد. برای همین می‌خواهد تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک مورد نیاز جاده‌ها را بشمارد. اما به‌دلیل اینکه درگیر آنالیز کردن پروژه عمرانی‌اش است، از شما می‌خواهد تا به او در این موضوع کمک کنید. توجه کنید از آن‌جا که جواب ممکن است بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ خروجی دهید. # ورودی در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد روستاها می‌باشد. در $n - 1$ خط بعدی، در هر خط دو عدد $u_i$ و $v_i$ می‌آید و بیانگر این است که جاده‌ای بین دو روستا با شماره‌های $u_i$ و $v_i$ باید احداث شود. تضمین می‌شود پس از احداث این $n - 1$ جاده، از هر روستایی با پیمایش جاده‌ها می‌توان به هر روستای دیگری رفت. $$1 \le n \le 1\ 000\ 000$$ $$1 \le u_i, v_i \le n$$ # خروجی در تنها خط خروجی، تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک را به باقیمانده $10^9 + 7$ بگویید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 3 ``` ## خروجی نمونه ۱ ``` 3 ``` می‌توان برای احداث جاده‌ی اول، از روستای شماره ۲ خاک برداشت، که در این‌صورت برای احداث جاده دوم می‌توان هم از روستای شماره ۱ و هم از روستای شماره ۳ خاک برداشت. همچنین اگر برای احداث جاده‌ی اول، از روستای شماره ۱ خاک برداریم، چون سوله واقع در روستای ۱، دقیقا یک تن خاک داشت، پس دیگر خاکی در آن باقی نمی‌ماند و مجبوریم از سوله واقع در روستای ۳ خاک برداریم. پس در کل به ۳ روش می‌توان سوله‌ها را برای برداشتن خاک انتخاب کرد. ## ورودی نمونه ۲ ``` 4 1 2 2 3 2 4 ``` ## خروجی نمونه ۲ ``` 7 ``` ## ورودی نمونه ۳ ``` 4 2 3 2 1 2 4 ``` ## خروجی نمونه ۳ ``` 7 ```

شرکت عمرانی سرداد

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

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

در پروژه‌ای که به آقا فیروز داده‌ شده، $n$ روستا وجود دارد که از $1$ تا $n$ شماره‌گذاری شده‌اند. همچنین یک لیست شامل $n - 1$ جاده به آقا فیروز داده‌ شده که هر جاده دوتا از روستاها را به هم وصل می‌کند. تضمین می‌شود پس از احداث جاده‌ها می‌توان با پیمایش تعدادی جاده از هر روستایی به هر روستای دیگری رفت.

همچنین در هر روستا، یک سوله وجود دارد که درون سوله واقع در روستای شماره $i$ ، دقیقا $i$ تن خاک وجود دارد. همچنین می‌دانیم برای احداث جاده‌ای بین دو روستای $u$ و $v$ ، باید دقیقا از یکی از این دو روستا، دقیقا ۱ تن خاک برداشت.

حال آقا فیروز که تازه استخدام شده‌، می‌خواهد خودی نشان دهد. برای همین می‌خواهد تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک مورد نیاز جاده‌ها را بشمارد. اما به‌دلیل اینکه درگیر آنالیز کردن پروژه عمرانی‌اش است، از شما می‌خواهد تا به او در این موضوع کمک کنید.

توجه کنید از آن‌جا که جواب ممکن است بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ خروجی دهید.

ورودی🔗

در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد روستاها می‌باشد.

در $n - 1$ خط بعدی، در هر خط دو عدد $u_i$ و $v_i$ می‌آید و بیانگر این است که جاده‌ای بین دو روستا با شماره‌های $u_i$ و $v_i$ باید احداث شود.

تضمین می‌شود پس از احداث این $n - 1$ جاده، از هر روستایی با پیمایش جاده‌ها می‌توان به هر روستای دیگری رفت. $1 \le n \le 1\ 000\ 000$ $1 \le u_i, v_i \le n$

خروجی🔗

در تنها خط خروجی، تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک را به باقیمانده $10^9 + 7$ بگویید.

مثال🔗

ورودی نمونه ۱🔗

3
1 2
1 3

خروجی نمونه ۱🔗

می‌توان برای احداث جاده‌ی اول، از روستای شماره ۲ خاک برداشت، که در این‌صورت برای احداث جاده دوم می‌توان هم از روستای شماره ۱ و هم از روستای شماره ۳ خاک برداشت. همچنین اگر برای احداث جاده‌ی اول، از روستای شماره ۱ خاک برداریم، چون سوله واقع در روستای ۱، دقیقا یک تن خاک داشت، پس دیگر خاکی در آن باقی نمی‌ماند و مجبوریم از سوله واقع در روستای ۳ خاک برداریم.

پس در کل به ۳ روش می‌توان سوله‌ها را برای برداشتن خاک انتخاب کرد.

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که پس از انجام پروژه عمرانی حسابی خسته شده بود، به خواب عمیقی فرو رفت. او که روابط اجتماعی قوی دارد، در خواب $n$ دوست فضانورد پیدا کرد که در نقاط مختلف کهکشان قرار داشتند. آن‌ها تصمیم گرفتند تا قراری بگذارند و یکدیگر را در سیاره زمین ملاقات کنند. هر نقطه از کهکشان یک نقطه سه بعدی در نظر گرفته می‌شود و به صورت مختصات $(x, y, z)$ نمایش داده می‌شود. زمین در نقطه $(0, 0, 0)$ قرار دارد. هر فضانورد در فضا می‌تواند در جهت یکی از سه بعد حرکت کند و به ازای هر یک واحد جابه‌جایی در یک بعد، یک واحد اکسیژن نیز مصرف می‌کند. از آ‌ن‌جایی که شارژ کردن کپسول اکسیژن هزینه بالایی دارد، آقا فیروز که دیگر تبدیل به یک مدیر کارکشته شده است، تصمیم می‌گیرد مجموع مصرف اکسیژن دوستان فضانوردش را کمینه کند. برای این‌کار او ایده‌ای را اجرایی می‌کند و بودجه مشخصی به آن اختصاص می‌دهد. آقا فیروز می‌خواهد دقیقا $a$ درگاه در جهت بعد اول مختصات یا همان $x$، $b$ درگاه در جهت بعد دوم یا همان $y$ و همچنین $c$ درگاه در جهت بعد سوم یا همان $z$ راه‌اندازی می‌کند. هر درگاه بدین صورت کار می‌کند که اگر یک فضانورد وارد آن درگاه شود، بدون نیاز به مصرف اکسیژن می‌توان آن را به هر درگاه دیگری در همان بعد ارسال کرد. همچنین هر درگاه بر اساس بعد خود یک مشخصه دارد که نشان‌دهنده مجموعه نقاطی است که شامل می‌شود. اگر یک درگاه در بعد $d$ ام خود دارای مشخصه $w$ باشد، تمام نقاطی که بعد $d$ ام آن‌ها برابر $w$ است را شامل می‌شود. در واقع هر درگاه نقاط یک صفحه در فضا را در بر می‌گیرد. حال آقا فیروز می‌خواهد طوری این درگاه‌ها را راه‌اندازی کند که مجموع اکسیژن مصرفی دوستان فضانوردش کمینه شود ولی مهارت‌های ریاضی او در خواب جوابگو نیستند. به او کمک کند تا خوابش تبدیل به رویا شود. # ورودی در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد فضانوردها می‌شود. در خط دوم، به ترتیب سه عدد $a$، $b$ و $c$ وارد می‌شوند که به ترتیب نمایانگر تعداد درگاه‌های بعد اول و دوم و سوم می‌باشد. در $i$امین خط از $n$ خط بعدی سه عدد $x_i$، $y_i$ و $z_i$ آمده‌اند که نمایانگر مختصات فعلی فضانورد $i$ام می‌باشند. $$1 \le n\le 100\ 000$$ $$0 \le a, b, c\le 100\ 000$$ $$0 \le x_i, y_i, z_i \le 10^9$$ # خروجی در تنها خط خروجی، کمینه اکسیژن مصرفی فضانوردان بعد از نصب درگاه‌ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 0 2 2 1 3 3 2 3 4 ``` ## خروجی نمونه ۱ ``` 4 ``` برای بعد دوم دو درگاه در $y=0$ و $y=3$ و برای بعد سوم دو درگاه در $z=0$ و $z=3$ می سازیم. در این حالت با مصرف ۴ اکسیژن همه‌ی فضانورد‌ها می‌توانند به زمین برسند. ## ورودی نمونه ۲ ``` 4 1 2 3 1 2 8 2 18 6 9 15 4 10 10 2 ``` ## خروجی نمونه ۲ ``` 36 ``` برای بعد اول یک درگاه در $x=5$، برای بعد دوم دو درگاه در $y=0$ و $y=15$ و برای بعد سوم سه درگاه در $z=0$ و $z=4$ و $z=6$ می‌سازیم. نفر اول با ۵ واحد اکسیژن از $(1, 2, 8)$ به $(0, 0, 6)$ می‌رود و با استفاده از درگاه $z=6$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود و به زمین می‌رسد. نفر دوم با ۵ واحد اکسیژن از $(2, 18, 6)$ به $(0, 15, 6)$ می‌رود. سپس با استفاده از درگاه $z=6$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود (اکنون در مختصات $(0, 15, 0)$ است) و دوباره با استفاده از درگاه $y=15$ بدون مصرف اکسیژن به درگاه $y=0$ می‌رود و به زمین می‌رسد. نفر سوم بدون مصرف اکسیژن از درگاه $y=15$ به درگاه $y=0$ می‌رود. سپس با مصرف ۹ واحد اکسیژن از $(9, 0, 4)$ به $(0, 0, 4)$ می‌رود و سپس با استفاده از درگاه $z=4$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود و به زمین می‌رسد. نفر چهارم با ۱۷ واحد اکسیژن از $(10, 10, 2)$ به $(0, 15, 0)$ می‌رود و با استفاده از درگاه $y=15$ به درگاه $y=0$ می‌رود و به زمین می‌رسد. ## ورودی نمونه ۳ ``` 3 0 0 0 1 3 1 2 1 3 3 2 2 ``` ## خروجی نمونه ۳ ``` 18 ``` در این حالت هیج ایستگاهی ساخته نمی‌شود و همه باید بدون استفاده از درگاه به زمین برسند.

اینتراستلار

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

آقا فیروز که پس از انجام پروژه عمرانی حسابی خسته شده بود، به خواب عمیقی فرو رفت. او که روابط اجتماعی قوی دارد، در خواب $n$ دوست فضانورد پیدا کرد که در نقاط مختلف کهکشان قرار داشتند. آن‌ها تصمیم گرفتند تا قراری بگذارند و یکدیگر را در سیاره زمین ملاقات کنند.

هر نقطه از کهکشان یک نقطه سه بعدی در نظر گرفته می‌شود و به صورت مختصات $(x, y, z)$ نمایش داده می‌شود. زمین در نقطه $(0, 0, 0)$ قرار دارد. هر فضانورد در فضا می‌تواند در جهت یکی از سه بعد حرکت کند و به ازای هر یک واحد جابه‌جایی در یک بعد، یک واحد اکسیژن نیز مصرف می‌کند.

از آ‌ن‌جایی که شارژ کردن کپسول اکسیژن هزینه بالایی دارد، آقا فیروز که دیگر تبدیل به یک مدیر کارکشته شده است، تصمیم می‌گیرد مجموع مصرف اکسیژن دوستان فضانوردش را کمینه کند.

برای این‌کار او ایده‌ای را اجرایی می‌کند و بودجه مشخصی به آن اختصاص می‌دهد. آقا فیروز می‌خواهد دقیقا $a$ درگاه در جهت بعد اول مختصات یا همان $x$ ، $b$ درگاه در جهت بعد دوم یا همان $y$ و همچنین $c$ درگاه در جهت بعد سوم یا همان $z$ راه‌اندازی می‌کند.

هر درگاه بدین صورت کار می‌کند که اگر یک فضانورد وارد آن درگاه شود، بدون نیاز به مصرف اکسیژن می‌توان آن را به هر درگاه دیگری در همان بعد ارسال کرد. همچنین هر درگاه بر اساس بعد خود یک مشخصه دارد که نشان‌دهنده مجموعه نقاطی است که شامل می‌شود. اگر یک درگاه در بعد $d$ ام خود دارای مشخصه $w$ باشد، تمام نقاطی که بعد $d$ ام آن‌ها برابر $w$ است را شامل می‌شود. در واقع هر درگاه نقاط یک صفحه در فضا را در بر می‌گیرد.

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

ورودی🔗

در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد فضانوردها می‌شود.

در خط دوم، به ترتیب سه عدد $a$ ، $b$ و $c$ وارد می‌شوند که به ترتیب نمایانگر تعداد درگاه‌های بعد اول و دوم و سوم می‌باشد.

در $i$ امین خط از $n$ خط بعدی سه عدد $x_i$ ، $y_i$ و $z_i$ آمده‌اند که نمایانگر مختصات فعلی فضانورد $i$ ام می‌باشند.

$1 \le n\le 100\ 000$ $0 \le a, b, c\le 100\ 000$ $0 \le x_i, y_i, z_i \le 10^9$

خروجی🔗

در تنها خط خروجی، کمینه اکسیژن مصرفی فضانوردان بعد از نصب درگاه‌ها را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

2 0 2 2
1 3 3
2 3 4

خروجی نمونه ۱🔗

برای بعد دوم دو درگاه در $y=0$ و $y=3$ و برای بعد سوم دو درگاه در $z=0$ و $z=3$ می سازیم.

در این حالت با مصرف ۴ اکسیژن همه‌ی فضانورد‌ها می‌توانند به زمین برسند.

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

برای بعد اول یک درگاه در $x=5$ ، برای بعد دوم دو درگاه در $y=0$ و $y=15$ و برای بعد سوم سه درگاه در $z=0$ و $z=4$ و $z=6$ می‌سازیم.

نفر اول با ۵ واحد اکسیژن از $(1, 2, 8)$ به $(0, 0, 6)$ می‌رود و با استفاده از درگاه $z=6$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود و به زمین می‌رسد.

نفر دوم با ۵ واحد اکسیژن از $(2, 18, 6)$ به $(0, 15, 6)$ می‌رود. سپس با استفاده از درگاه $z=6$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود (اکنون در مختصات $(0, 15, 0)$ است) و دوباره با استفاده از درگاه $y=15$ بدون مصرف اکسیژن به درگاه $y=0$ می‌رود و به زمین می‌رسد.

نفر سوم بدون مصرف اکسیژن از درگاه $y=15$ به درگاه $y=0$ می‌رود. سپس با مصرف ۹ واحد اکسیژن از $(9, 0, 4)$ به $(0, 0, 4)$ می‌رود و سپس با استفاده از درگاه $z=4$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود و به زمین می‌رسد.

نفر چهارم با ۱۷ واحد اکسیژن از $(10, 10, 2)$ به $(0, 15, 0)$ می‌رود و با استفاده از درگاه $y=15$ به درگاه $y=0$ می‌رود و به زمین می‌رسد.

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

در این حالت هیج ایستگاهی ساخته نمی‌شود و همه باید بدون استفاده از درگاه به زمین برسند.