+ محدودیت زمان: ۷ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شاختک که برای عملیاتی حیاتی به قزاقستان دو بعدی رفته بود، ناگهان یک‌ دل نه صد دل عاشق پرنسسی شد و عملیات به کلی از یادش رفت. پرنسس در ۱۲۶ امین طبقه‌ی قلعه‌ای بسیار بلند زندگی می‌کند و شاختک قصد دارد نامه‌ی عاشقانه‌ی خود را به دست او برساند. به همین جهت، $n$ مستطیل تهیه کرده تا با روی هم چیدن آن‌ها، بتواند برجی بسازد تا خود را به پنجره‌ی اتاق پرنسس برساند. از آن‌جایی که قزاقستان دو بعدی کشور زلزله‌خیزی است، برای ساخت برج به نحوی که برج نریزد، قوانین زیر می‌بایست رعایت شوند. + هر مستطیل روی یک مستطیل دیگر و یا روی زمین باید قرار داشته باشد. + هر مستطیل را می‌توان هم به صورت عمودی و هم به صورت افقی‌ روی برج قرار داد. (به شرطی که تمام قوانین دیگر رعایت شوند.) + تنها یک مستطیل می‌تواند روی زمین باشد. + برای هر مستطیل $A$ می‌توان مستطیل ‌$B$ را روی آن گذاشت اگر و تنها اگر ضلعی که از مستطیل $B$ روی ضلع مستطیل $A$ قرار می‌گیرد، اکیدا از آن کوچک‌تر باشد. + همه مستطیل‌ها باید استفاده شوند. شاختک هنگام خرید مستطیل‌ها، دقت کرده روشی وجود داشته باشد که $n$ مستطیل مورد نظر با رعایت قوانین فوق بتوانند روی هم قرار گیرند. شاختک که از ارتفاع طبقه‌ی ۱۲۶ ام قلعه‌ی پرنسس اطلاعی ندارد، قصد دارد با مستطیل‌های خریداری شده بلند‌ترین برج ممکن را بسازد. به او کمک کنید و طول بلند‌ترین برج قابل ساخت را محاسبه کنید. # ورودی در خط اول ورودی، عدد $n$ آمده که نشان دهنده تعداد مستطیل‌‌هاست. در $n$ خط بعدی، در هر خط ۲ عدد $a$ و $b$ آمده که نشان‌دهنده‌ی طول و عرض مستطیل $i$ام است. $$ 1 \le n \le 250 \, 000$$ $$1 \le a, b \le 10^9$$ توجه کنید که ممکن است مشخصات دو مستطیل یکسان باشد. # خروجی طول بلندترین برج ممکن را خروجی دهید به طوری که تمام قوانین رعایت شود. # مثال ## ورودی نمونه ۱ ``` 3 50000 160000 50000 100000 50000 100000 ``` ## خروجی نمونه ۱ ``` 200000 ```

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