+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای پستچی بترین پستچی دنیاست! برای همین ماموریتی عظیم را به او داده‌اند: ماجرا از این قرار است که روزی عمو(که فردی بسیار پول پرست است) در حال ساختمان سازی بود و برای ساختن ساختمانش نیاز داشت که سنگی بسیار بزرگ و سنگین را جابه‌جا کند. او جرثقیلی را برای این کار به کار گرفت اما حین جابه‌جایی، زنجیرهای بسته شده به سنگ پاره شد و سنگ از بالا دقیقا افتاد روی پست‌خانه‌ای که آقای پستچی در آن جا کار می‌کرد و سقف را سوراخ کرد و به زمین خورد. متاسفانه هنگامی که از عمو درخواست خسارت شد، او ابتدا تعدادی تمبر به سنگ چسباند و ادعا کرد که می‌خواست سنگ را به پست‌خانه بیاورد تا آن را پست کند اما چون سنگ از در رد نمی‌شد تصمیم گرفت که آن را روی سقف پستخانه بگذارد اما به علت ضعیف و فرسوده بودن سقف، سنگ سقف را سوراخ کرد و به زمین افتاد! سپس او از مسئولین پست‌خانه خواست که سنگ را برایش پست کنند و در نهایت خونسردی تمبر بیشتری به سنگ چسباند تا سنگ را با پست پیشتاز پست کنند! مسئولین هم این کار را به آقای پستچی(بترین پستچی دنیا) سپردند. آقای پستچی برای بلند کردن این سنگ، باید زورش درجه ۱ شود! اما الان زورش درجه $n$ است. او برای بهبود درجه‌ی زورش به ورزش روی آورده است و به باشگاه بدنسازی می‌رود. در اینجا دو حالت پیش می‌آید: ۱- اگر درجه‌ی زور آقای پستچی فرد باشد، وقت این است که مکمل بخورد و این مکمل‌ها درجه‌ی زور ایشان را از $n$ به $3n+3$ افزایش می‌دهند. اما عوضش او را برای ورزش کردن آماده می‌سازند. ۲- اگر درجه‌ی زور آقای پستچی زوج باشد، وقت این است که او ورزش کند و با این کار درجه‌ی زور او نصف می‌شود. حالا آقای پست‌چی می‌خواهد بداند که اصلا امکان دارد که درجه‌ی زور او ۱ شود یا نه؛ چرا که اگر نمی‌شود، او می‌خواهد هر چه سریعتر از این ماموریت استعفا دهد تا پول صرف بدنسازی نکند.(دارد پول‌هایش را جمع می‌کند تا موتور پستش را ارتقاء دهد) # ورودی در تنها سطر ورودی عدد $n$ آمده است که نمایانگر درجه‌ی زور اولیه‌ی آقای پستچی است. $$ 1 \le n \le 10^{14} $$ # خروجی در تنها سطر خروجی بگویید که زور آقای پستچی بالاخره درجه‌ ۱ می‌شود یا خیر. اگر زورش درجه ۱ خواهد شد، "Yes" و اگر نه "No" را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 8 ``` ## خروجی نمونه ۱ ``` Yes ``` ## ورودی نمونه ۲ ``` 3 ``` ## خروجی نمونه ۲ ``` No ```

سنگ برنده

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

آقای پستچی بترین پستچی دنیاست! برای همین ماموریتی عظیم را به او داده‌اند:

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

متاسفانه هنگامی که از عمو درخواست خسارت شد، او ابتدا تعدادی تمبر به سنگ چسباند و ادعا کرد که می‌خواست سنگ را به پست‌خانه بیاورد تا آن را پست کند اما چون سنگ از در رد نمی‌شد تصمیم گرفت که آن را روی سقف پستخانه بگذارد اما به علت ضعیف و فرسوده بودن سقف، سنگ سقف را سوراخ کرد و به زمین افتاد! سپس او از مسئولین پست‌خانه خواست که سنگ را برایش پست کنند و در نهایت خونسردی تمبر بیشتری به سنگ چسباند تا سنگ را با پست پیشتاز پست کنند! مسئولین هم این کار را به آقای پستچی(بترین پستچی دنیا) سپردند. آقای پستچی برای بلند کردن این سنگ، باید زورش درجه ۱ شود! اما الان زورش درجه $n$ است. او برای بهبود درجه‌ی زورش به ورزش روی آورده است و به باشگاه بدنسازی می‌رود. در اینجا دو حالت پیش می‌آید:

۱- اگر درجه‌ی زور آقای پستچی فرد باشد، وقت این است که مکمل بخورد و این مکمل‌ها درجه‌ی زور ایشان را از $n$ به $3n+3$ افزایش می‌دهند. اما عوضش او را برای ورزش کردن آماده می‌سازند.

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

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

ورودی🔗

در تنها سطر ورودی عدد $n$ آمده است که نمایانگر درجه‌ی زور اولیه‌ی آقای پستچی است. $1 \le n \le 10^{14}$

خروجی🔗

در تنها سطر خروجی بگویید که زور آقای پستچی بالاخره درجه‌ ۱ می‌شود یا خیر. اگر زورش درجه ۱ خواهد شد، "Yes" و اگر نه "No" را خروجی دهید.

مثال🔗

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

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

Yes

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

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

No

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای پستچی بترین پستچی دنیاست! با این حال او می‌خواهد روز‌های کاری مفیدی داشته باشد. به او $n$ بسته‌ی پستی داده شده است که $i$امین بسته را باید به خانه‌ی با کد پستی $a_i$ تحویل دهد. آقای پستچی عادت بدی دارد؛ در هر روز کاری او می‌تواند تعدادی بسته برداشته و به مقصد یکی از آن‌ها برود، آن را تحویل دهد و سپس به مقصدی برود که کدپستی‌اش دقیقا یکی بعد از کد پستی مقصد کنونی است! یعنی اگر کد پستی محلی که آقای پستچی بسته را تحویل داده برابر $a_i$ است، کد پستی بسته‌ی بعدی باید $a_i+1$ باشد. او آنقدر این‌کار را می‌کند تا بسته‌های همراهش تمام شوند و یا بسته‌ای با کد پستی بعدی همراه خود نبرده باشد. آقای پستچی می‌تواند این $n$ بسته را در تعداد دلخواهی روز و به ترتیبی دلخواه به مقصدشان تحویل دهد؛ تنها خواسته‌ی قلبی او این است که طوری کار کند که احساس کم‌کاری نکند. مثلا اگر روزی باشد که تنها یک بسته تحویل دهد، احساس کم‌کاری میکند و گریان به خانه بازمیگردد. اگر روزی دو بسته تحویل دهد، بسیار بهتر از روزهاییست که تنها یک بسته تحویل داده اما باز هم غم کم‌کاری و احساس گناه تمام وجودش را فرا می‌گیرد. خلاصه آقای پستچی دنبال برنامه‌ای برای تحویل این $n$ بسته‌ی پستی است که کمترین تعداد بسته‌ای که در یک روز تحویل مشتری می‌دهد، بیشینه باشد. برای مثال او همیشه می‌تواند بسته‌ها را در $n$ روز تحویل دهد، هر روز یک بسته. اما این بسیار عذاب وجدان آور است! ولی اگر کد پستی مقصد همه‌ی $n$ بسته یکسان باشد، آقای پستچی چاره‌ای جز این‌کار ندارد! # ورودی در تنها سطر ورودی عدد $n$ آمده‌است که نمایانگر تعداد بسته‌های پستی می‌باشد. سپس در سطر بعدی، $n$ عدد آمده‌است که عدد $i$ام نمایانگر $a_i$ می‌باشد. $$0 \le n \le 1\ 000 $$ $$1 \le a_i \le 10\ 000$$ توجه کنید که ممکن است برای یک کد پستی، چند بسته در دست تحویل باشد. در این صورت هریک باید در روزی جداگانه تحویل داده شوند. # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر بیشترین تعداد بسته‌ی ممکن است که آقای پستچی می‌تواند طوری بسته‌ها را تحویل دهد که در هر روز حداقل آن تعداد بسته را به دست صاحبش برساند. # مثال ## ورودی نمونه ۱ ``` 10 1 2 3 4 5 10 9 8 7 6 ``` ## خروجی نمونه ۱ ``` 10 ``` در این نمونه آقای پستچی در یک روز می‌تواند همه‌ی ۱۰ بسته را تحویل دهد. ## ورودی نمونه ۲ ``` 5 1 2 3 4 9 ``` ## خروجی نمونه ۲ ``` 1 ``` یک روش برای آقای پستچی تحویل بسته‌ به مقاصد ۱ و ۲ در اولین روز کاری و بسته به مقاصد ۳ و ۴ در دومین روز کاری و تحویل بسته با مقصد ۹ در روز سوم است. ## ورودی نمونه ۳ ``` 0 ``` ## خروجی نمونه ۳ ``` 0 ``` این هم حالتی خاص که بسته‌ای وجود ندارد؛ کاملا هم منطقیست! ## ورودی نمونه ۴ ``` 2 2 2 ``` ## خروجی نمونه ۴ ``` 1 ```

روزهای کم‌کاری

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

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

به او $n$ بسته‌ی پستی داده شده است که $i$ امین بسته را باید به خانه‌ی با کد پستی $a_i$ تحویل دهد. آقای پستچی عادت بدی دارد؛ در هر روز کاری او می‌تواند تعدادی بسته برداشته و به مقصد یکی از آن‌ها برود، آن را تحویل دهد و سپس به مقصدی برود که کدپستی‌اش دقیقا یکی بعد از کد پستی مقصد کنونی است! یعنی اگر کد پستی محلی که آقای پستچی بسته را تحویل داده برابر $a_i$ است، کد پستی بسته‌ی بعدی باید $a_i+1$ باشد. او آنقدر این‌کار را می‌کند تا بسته‌های همراهش تمام شوند و یا بسته‌ای با کد پستی بعدی همراه خود نبرده باشد.

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

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

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

ورودی🔗

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

سپس در سطر بعدی، $n$ عدد آمده‌است که عدد $i$ ام نمایانگر $a_i$ می‌باشد. $0 \le n \le 1\ 000$ $1 \le a_i \le 10\ 000$

توجه کنید که ممکن است برای یک کد پستی، چند بسته در دست تحویل باشد. در این صورت هریک باید در روزی جداگانه تحویل داده شوند.

خروجی🔗

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

مثال🔗

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

10
1 2 3 4 5 10 9 8 7 6

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

در این نمونه آقای پستچی در یک روز می‌تواند همه‌ی ۱۰ بسته را تحویل دهد.

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

5
1 2 3 4 9

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

یک روش برای آقای پستچی تحویل بسته‌ به مقاصد ۱ و ۲ در اولین روز کاری و بسته به مقاصد ۳ و ۴ در دومین روز کاری و تحویل بسته با مقصد ۹ در روز سوم است.

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

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

این هم حالتی خاص که بسته‌ای وجود ندارد؛ کاملا هم منطقیست!

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

2
2 2

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای پستچی بترین پستچی دنیاست! از این رو او انتخاب شده‌است که تی‌شرت‌های Quera را به دست برندگانش برساند. در مسابقات اخیر Quera، $n$ نفر برنده‌ی تی‌شرت شده‌اند که $n$ نفر اول در رتبه‌بندی امتیازی سایت هستند. آقای پستچی این $n$ تی‌شرت را بار زد تا به برندگانش برساند؛ اما ناگهان رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که فردی تنبل طماع است جلویش سبز شد. رادزینکا آقای پستچی را به گوشه‌ای برد تا رازی را برای او بازگو کند. گویا رادزینکا کسی است که پیش از آقای پستچی مسئول رساندن جوایز به برندگان Quera بوده‌است. او از برندگان عجیب مسابقات Quera برای آقای پستچی می‌گوید. در گذشته، رادزینکا همیشه با جیب خالی به سراغ تحویل جوایز می‌رفته. (آقای پستچی هم همینگونه‌است، پس بسیار جذب صحبت‌های رادزینکا می‌شود.) همیشه هنگام تحویل جایزه به هر فرد برنده این اتفاقات می‌افتد: ابتدا برنده مقدار پولی که فرد جایزه‌رسان همراه دارد را می‌پرسد. اگر فرد برنده در Quera رتبه‌ی $x$ داشته باشد، تنها زمانی راضی می‌شود که مقدار پول جایزه‌رسان مضربی طبیعی از $x$ باشد. اگر در ابتدا مقدار پول همراه جایزه‌رسان مضربی طبیعی از $x$ بود، فرد برنده جایزه‌ی خود را با رضایت تحویل می‌گیرد و به خانه‌ی خود می‌برد. اما اگر نبود، مکافات شروع می‌شود. فرد شماره $x$ جایزه‌رسان را تا یک بانک می‌برد تا مقداری پول بردارد و به او بدهد. (هرچه پستچی اصرار کند که او نیازی نیست پول بدهد، گوش فرد برنده بدهکار نخواهد بود!) پس از رفتن به بانک، اگر جایزه‌رسان ۰ تومان پول همراهش بود، فرد شماره $x$ مقدار $x$ تومان به او پول می‌دهد. وگرنه به‌اندازه‌ی کوچکترین ضریبی از پول کنونی جایزه‌رسان از بانک برداشته و به او می‌دهد تا پول او به $x$ بخش‌پذیر شود. (چون معمولا این مقدار از ۲۰۰۰۰۰ تومان بیشتر است، این عملیات بسیار طول می‌کشد!) آقای پستچی پس از شنیدن این خاطرات، به فکر فرو می‌رود. برای او مقدار پولی که دریافت می‌کند اهمیتی ندارد؛ تنها زمان برای او مهم است. با توجه به خاطرات رادزینکا، مقدار زمانی که طول می‌کشد تا آقای پستچی بسته‌ها را تحویل دهد به تعداد بار‌هایی که برندگان اون را به بانک می‌برند ربط دارد و این به ترتیب رساندن جوایز مربوط است. بعنوان مثال اگر $n = 3$ و آقای پستچی جوایز را به ترتیب به رتبه‌ی ۱ تا ۳ بدهد، هریک از ۳ برنده او را تا بانک می‌برند. اما اگر ابتدا او جایزه‌ را به رتبه‌ی ۲ برساند و سپس رتبه‌ی ۱ و در آخر رتبه‌ی ۳، افراد با رتبه‌های ۲ و ۳ او را تا بانک می‌برند و رتبه‌ی ۱ وقت او را نمی‌گیرد. آقای پستچی می‌خواهد اهمیت این ترتیب افراد را بفهمد؛ پس می‌خواهد بداند که اختلاف تعداد بانک رفتن در بیشترین و کمترین حالت ممکن (از همه‌ی $n!$ ترتیب ممکن جایزه‌رسانی) چقدر است. # ورودی در تنها سطر ورودی عدد $n$ آمده‌است که نمایانگر تعداد برندگان می‌باشد. $$1 \le n \le 10^{10} $$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر اختلاف تعداد بانک رفتن در بیشترین و کمترین حالت ممکن (از همه‌ی $n!$ ترتیب ممکن جایزه‌رسانی) است. # مثال ## ورودی نمونه ۱ ``` 3 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 1 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 6 ``` ## خروجی نمونه ۳ ``` 2 ```

برندگان عجیب

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

آقای پستچی بترین پستچی دنیاست! از این رو او انتخاب شده‌است که تی‌شرت‌های Quera را به دست برندگانش برساند.

در مسابقات اخیر Quera، $n$ نفر برنده‌ی تی‌شرت شده‌اند که $n$ نفر اول در رتبه‌بندی امتیازی سایت هستند. آقای پستچی این $n$ تی‌شرت را بار زد تا به برندگانش برساند؛ اما ناگهان رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که فردی تنبل طماع است جلویش سبز شد. رادزینکا آقای پستچی را به گوشه‌ای برد تا رازی را برای او بازگو کند.

گویا رادزینکا کسی است که پیش از آقای پستچی مسئول رساندن جوایز به برندگان Quera بوده‌است. او از برندگان عجیب مسابقات Quera برای آقای پستچی می‌گوید. در گذشته، رادزینکا همیشه با جیب خالی به سراغ تحویل جوایز می‌رفته. (آقای پستچی هم همینگونه‌است، پس بسیار جذب صحبت‌های رادزینکا می‌شود.) همیشه هنگام تحویل جایزه به هر فرد برنده این اتفاقات می‌افتد: ابتدا برنده مقدار پولی که فرد جایزه‌رسان همراه دارد را می‌پرسد. اگر فرد برنده در Quera رتبه‌ی $x$ داشته باشد، تنها زمانی راضی می‌شود که مقدار پول جایزه‌رسان مضربی طبیعی از $x$ باشد. اگر در ابتدا مقدار پول همراه جایزه‌رسان مضربی طبیعی از $x$ بود، فرد برنده جایزه‌ی خود را با رضایت تحویل می‌گیرد و به خانه‌ی خود می‌برد. اما اگر نبود، مکافات شروع می‌شود. فرد شماره $x$ جایزه‌رسان را تا یک بانک می‌برد تا مقداری پول بردارد و به او بدهد. (هرچه پستچی اصرار کند که او نیازی نیست پول بدهد، گوش فرد برنده بدهکار نخواهد بود!)

پس از رفتن به بانک، اگر جایزه‌رسان ۰ تومان پول همراهش بود، فرد شماره $x$ مقدار $x$ تومان به او پول می‌دهد. وگرنه به‌اندازه‌ی کوچکترین ضریبی از پول کنونی جایزه‌رسان از بانک برداشته و به او می‌دهد تا پول او به $x$ بخش‌پذیر شود. (چون معمولا این مقدار از ۲۰۰۰۰۰ تومان بیشتر است، این عملیات بسیار طول می‌کشد!)

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

بعنوان مثال اگر $n = 3$ و آقای پستچی جوایز را به ترتیب به رتبه‌ی ۱ تا ۳ بدهد، هریک از ۳ برنده او را تا بانک می‌برند. اما اگر ابتدا او جایزه‌ را به رتبه‌ی ۲ برساند و سپس رتبه‌ی ۱ و در آخر رتبه‌ی ۳، افراد با رتبه‌های ۲ و ۳ او را تا بانک می‌برند و رتبه‌ی ۱ وقت او را نمی‌گیرد.

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

ورودی🔗

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

$1 \le n \le 10^{10}$

خروجی🔗

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

مثال🔗

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

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

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای پستچی بترین پستچی دنیاست! در نتیجه او ارتقاء درجه گرفته و باید $k$ پست‌خانه‌ از بین $n$ پست‌خانه‌ی شهر را انتخاب کند و مسئول آن‌ها شود. اگر شهر را از بالا نگاه کنیم مانند صفحه‌ی مختصات دکارتی می‌شود که پست‌خانه‌ی $i$، در نقطه‌ی ($y_i$،$x_i$) است. از آنجایی که آقای پستچی انسان بسیار پرکاری می‌باشند، می‌خواهند جوری پست‌خانه‌ها را انتخاب کنند که مساحت زیر پوشش پست‌خانه‌های انتخابی ایشان بیشینه شود. مساحت زیر پوشش مجموعه‌ای از پست‌خانه‌ها، همان پوش محدب آن‌ها می‌باشد.(برای دریافت اطلاعات بیشتر درباره‌ی پوش محدب به [ اینجا ](https://fa.wikipedia.org/wiki/%D9%BE%D9%88%D8%B4_%D9%85%D8%AD%D8%AF%D8%A8) مراجعه کنید) آقای پستچی می‌خواهد حجم کارش را بداند. از این رو از شما می‌خواهد که به او بگویید این مساحت بیشینه چقدر می‌باشد. # ورودی در سطر اول ورودی به ترتیب دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد پست‌خانه‌های شهر و تعداد پست‌خانه‌هایی است که آقای پستچی انتخاب می‌کند. سپس در $n$ خط بعدی در خط $i$، به ترتیب $x_i$ و $y_i$ آمده است که نمایانگر مختصات پست‌خانه $i$ می‌باشد. مختصات هیچ پست‌خانه‌ای بیشتر از یک بار نمی‌آید. $$ 3 \le k \le n \le 40 $$ $$ 0 \le x_i , y_i \le 1\ 000 $$ # خروجی در تنها سطر خروجی باید جواب را با دقیقا یک رقم اعشار خروجی دهید. # مثال ## ورودی نمونه ``` 7 4 2 2 1 5 6 1 5 5 3 7 7 6 9 4 ``` ## خروجی نمونه ``` 24.0 ``` توضیح: در نمونه‌ی بالا پست‌خانه‌های (۲،۲) ، (۶،۱) ، (۹،۴) و (۳،۷) را انتخاب می‌کنیم که مجموع مساحت زیر پوشش آن‌ها ۲۴ می‌شود.

انتخاب پست‌خانه

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

آقای پستچی بترین پستچی دنیاست! در نتیجه او ارتقاء درجه گرفته و باید $k$ پست‌خانه‌ از بین $n$ پست‌خانه‌ی شهر را انتخاب کند و مسئول آن‌ها شود. اگر شهر را از بالا نگاه کنیم مانند صفحه‌ی مختصات دکارتی می‌شود که پست‌خانه‌ی $i$ ، در نقطه‌ی ( $y_i$ ، $x_i$ ) است. از آنجایی که آقای پستچی انسان بسیار پرکاری می‌باشند، می‌خواهند جوری پست‌خانه‌ها را انتخاب کنند که مساحت زیر پوشش پست‌خانه‌های انتخابی ایشان بیشینه شود. مساحت زیر پوشش مجموعه‌ای از پست‌خانه‌ها، همان پوش محدب آن‌ها می‌باشد.(برای دریافت اطلاعات بیشتر درباره‌ی پوش محدب به اینجا مراجعه کنید) آقای پستچی می‌خواهد حجم کارش را بداند. از این رو از شما می‌خواهد که به او بگویید این مساحت بیشینه چقدر می‌باشد.

ورودی🔗

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

سپس در $n$ خط بعدی در خط $i$ ، به ترتیب $x_i$ و $y_i$ آمده است که نمایانگر مختصات پست‌خانه $i$ می‌باشد. مختصات هیچ پست‌خانه‌ای بیشتر از یک بار نمی‌آید. $3 \le k \le n \le 40$ $0 \le x_i , y_i \le 1\ 000$

خروجی🔗

در تنها سطر خروجی باید جواب را با دقیقا یک رقم اعشار خروجی دهید.

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

24.0

توضیح: در نمونه‌ی بالا پست‌خانه‌های (۲،۲) ، (۶،۱) ، (۹،۴) و (۳،۷) را انتخاب می‌کنیم که مجموع مساحت زیر پوشش آن‌ها ۲۴ می‌شود.