- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
امین \(n\) دوست دارد. او دوستهایش را با اعداد \(1\) تا \(n\) شمارهگذاری کرده است. هر کدام از دوستهای امین از سه نظر «مهارت در فرانتاند» که با \(f_i\)، «مهارت در بکاند» که با \(b_i\) و «پول نقد در حساب» که با \(m_i\) نشانمیدهیم، برای دعوت در یک مهمانی کاندید شدهاند.
دوست \(i\)ام امین نسبت به دوست \(j\)ام امین «احساس حقارت» میکند. اگر در هر دو زمینه فرانتاند و بکاند مهارت کمتری داشته باشد. به عبارت دیگر \(f_i < f_j\) و \(b_i < b_j\) باشد، دوست \(i\)ام امین نسبت به دوست \(j\)ام «احساس حقارت» میکند. (توجه کنید میزان پول نقد در حساب اهمیتی ندارد!)
حال امین میخواهد تعدادی از دوستان خود را انتخاب کند، تا با هم استارتآپ بزنند. امین میخواهد طوری این جمع را انتخاب کند که:
- هیچ دو نفری نسبت به هم احساس حقارت نکنند.
- مجموع پول نقد در حساب این افراد بیشینه باشد.
به امین کمک کنید تا بیشترین مجموع پول نقدی که میتواند با کمک دوستانش برای تاسیس استارتاپ جمع کند را حساب کند.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(n\) آمده است که تعداد دوستان امین را نشان میدهد. \[1 \leq n \leq 100 \, 000\] در \(n\) سطر بعدی در هر سطر سه عدد صحیح \(f_i\)، \(b_i\) و \(m_i\) که با یک فاصله از هم جدا شدهاند و به ترتیب نشاندهنده مهارت در فرانت، مهارت در بکاند و پول نقد در حساب افراد را نشان میدهد.
\[1 \leq f_i, b_i, m_i \leq 10^9\]
خروجی
در سطر اول خروجی، بیشترین مجموع پول نقدی که میتواند با کمک دوستانش برای تاسیس استارتاپ جمع کند را حساب کنید.
مثال
ورودی نمونه ۱
3
1 1 100
2 3 50
3 2 50
خروجی نمونه ۱
100
امین میتواند دوست ۱ خود را برای تاسیس استارتآپ انتخاب کند. بنابراین میتواند ۱۰۰ تومان پول نقد داشته باشد.
توجه کنید دوست ۱ با هیچ دوست دیگری نمیتواند انتخاب شود، چون نسبت به آنها احساس حقارت میکند. همچنین مجموع پول نقد ۲ و ۳ حداکثر ۱۰۰ تومان است. پس تاسیس این استارتآپ با پول بیشتری ممکن نیست.
ورودی نمونه ۲
4
1 1 100
2 3 50
3 2 50
3 3 50
خروجی نمونه ۲
150
امین میتواند دوست ۲، ۳ و ۴ خود را برای تاسیس استارتآپ انتخاب کند. بنابراین میتواند ۱۵۰ تومان پول نقد داشته باشد.
توجه کنید ۱ و ۲ نسبت به ۳ احساس حقارت نمیکنند، چون باید در هر دو مبحث فرانتاند و بکاند مهارت کمتری داشتهباشند ولی در یکی از اینویژگیها برابر هستند.
همچنین با بررسی کردن حالتهای مختلف میتوان نشان داد که این عدد بیشینه است.