====== Disjoint Rectangles ======



به یک مستطیل ‎«مستطیل منظم»‎ می‌گوییم اگر این مستطیل بطور کامل درون ربع اول صفحه مختصات بیفتد (‎ربع اول صفحه مختصات، نقاطی را شامل می‌شود که هم ‎$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$‎.

===== محدودیت‌ها =====


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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|3‎ \\ 0 10 2 5 3‎ \\ 2 4 0 4 4‎ \\ 5 6 0 10 2 | 6 |

</WRAP>
  * [[سوال ۷|سوال بعد]]
  * [[سوال ۵|سوال قبل]]
‎