+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که پس از انجام پروژه عمرانی حسابی خسته شده بود، به خواب عمیقی فرو رفت. او که روابط اجتماعی قوی دارد، در خواب $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 ``` در این حالت هیج ایستگاهی ساخته نمی‌شود و همه باید بدون استفاده از درگاه به زمین برسند. <details class="blue"> <summary> راهنمایی ۱ </summary> سوال را برای تمامی بعد‌ها جداگانه حل می‌کنیم. به جای آنکه بخواهیم دقیقا $a$ تا درگاه بگذاریم فرض می‌کنیم که هزینه ساخت هر‌ درگاه $w$ اکسیژن است و با استفاده از باینری‌سرچ، $w$ را به نحوی مشخص می‌کنیم که حالت بهینه‌ای با $a$ درگاه وجود داشته باشد. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> حال مساله بالا را به این شکل حل می‌کنیم: مختصات‌های افراد را مرتب می‌کنیم و دنباله مرتب شده را $a$ می‌نامیم. تعریف می‌کنیم: $dp_i$ کمترین مقدار اکسیژن مصرفی برای $i$ فضانورد اول به طوری که یک درگاه در نقطه $a_i$ قرار گرفته باشد. به ازای هر‌نقطه $j$ به طوری که $j<i$، $ans_j$ را کمترین مقدار اکسیژن مصرفی تعریف می‌کنیم به طوری که افراد $j+1$ تا $i$ به درگاه واقع در نقطه $a_i$ بروند و افراد ۱ تا $j$ به زمین برسند. به ازای هر‌نقطه $j$ به طوری که $j<i$، $val_j$ را کمترین مقدار اکسیژن مصرفی تعریف می‌کنیم به طوری که دو درگاه بر روی نقطه $a_i$ و $a_j$ باشد و افراد $j+1$ تا $i$ به درگاه واقع در نقطه $a_i$ بروند و افراد ۱ تا $j$ به زمین برسند. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> می‌توان $ans$ و $val$ را با استفاده از $trick$ $hull$ $convex$ بدست آورد. آرایه $dp$ به کمک $ans$ و $val$ حساب می‌شود و کمترین اکسیژن مصرفی را به کمک آرایه $dp$ حساب می‌کنیم. </details>

حل سؤال در بانک سؤالات