به یک مستطیل ‎«مستطیل منظم»‎ می‌گوییم اگر این مستطیل بطور کامل درون ربع اول صفحه مختصات بیفتد (‎ربع اول صفحه مختصات، نقاطی را شامل می‌شود که هم ‎$x$‎ آنها و هم ‎$y$‎‌ آنها بزرگتر یا مساوی صفر باشد‎(‎ و حداقل یکی از اضلاع آن منطبق بر یکی از محور‌های مختصات باشد. در این مسئله به شما ‎$n$‎ مستطیل منظم وزن‌دار داده شده است و شما باید برنامه‌ای بنویسید که زیر مجموعه‌ای از این مستطیل‌ها را بیابد که مستطیل‌های درون آن دو به دو مجزا باشند و وزن آن بیشینه شود. دو مستطیل مجزا هستند اگر مساحت اشتراک آن‌ها برابر با صفر باشد (‎دقت کنید که مساحت یک نقطه یا خط برابر با صفر است)‎ و همچنین وزن یک مجموعه از مستطیل‌ها برابر با مجموع وزن مستطیل‌های آن می‌باشد.

• در سطر اول ورودی عدد صحیح ‎$n$‎ آمده است که نشان‌دهنده تعداد مستطیل‌ها می‌باشد.
• در ‎$n$‎ سطر بعدی در هر سطر ‎$5$‎ عدد صحیح ‎$x_1$‎، ‎$x_2$‎، ‎$y_1$‎، ‎$y_2$‎ و ‎$w$‎ آمده است که مشخصات مستطیل ‎$i$‎ام را نشان می‌دهد. ‎$x_1$‎ و ‎$x_2$‎ به ترتیب نشان‌گر مختصه ‎$x$‎ ضلع‌های سمت چپ و سمت راست مستطیل می‌باشند. ‎$y_1$‎‌ و ‎$y_2$‎ هم به ترتیب نشان‌گر مختصه ‎$y$‎ ضلع‌های پایین و بالای مستطیل می‌باشند و ‎$w$‎ نیز وزن مستطیل می‌باشد.
• ‎ $1 \leq n \leq 7000$‎.
• ‎ $0 \leq w \leq 10^9$‎.
• ‎ $0 \leq x_1 < x_2 \leq 10^9$‎و ‎$0 \leq y_1 < y_2 \leq 10^9$‎.
• ضمانت می‌شود تمام مستطیل‌های ورودی مستطیل‌های منظم هستند.

در تنها سطر خروجی وزنِ پر‌وزن‌ترین زیرمجموعه مجزا از مستطیل‌های داده شده را چاپ کنید‎.

• زیرمساله‌ی اول (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 500$‎.
• زیرمساله‌ی دوم (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 2500$‎.
• زیرمساله‌ی سوم (۴۰ نمره): در همه‌ی تست‌ها ‎$n\leq 7000$‎.

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

• سوال بعد
• سوال قبل

‎