+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که پس از انجام پروژه عمرانی حسابی خسته شده بود، به خواب عمیقی فرو رفت. او که روابط اجتماعی قوی دارد، در خواب $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 ``` در این حالت هیج ایستگاهی ساخته نمی‌شود و همه باید بدون استفاده از درگاه به زمین برسند.