- محدودیت زمان: ٢ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون مقدماتی دوم دوره ۲۷ المپیاد کامپیوتر
مهسا در بازی فرار از خانه غولها شرکت کردهاست! روال بازی این است که شما ابتدا درون خانه قرار میگیرید و باید از غولها فرار کنید و از خانه بیرون بیایید. اما مهسا میخواهد بهجای فرار از غولها، آنها را به تسخیر در آورد!
در این خانه \(n\) غول وجود دارد. غول \(i\) ، \(a_i\) قدرت دارد و اگر مهسا بخواهد آن غول را به تسخیر در بیاورد، یا باید حداقل \(b_i\) ( \(a_i \le b_i\) ) قدرت داشته باشد، یا \(c_i\) تومن به غول پول بدهد. قدرت مهسا ابتدا صفر است. قدرت هر غولی که مهسا تسخیر کند به او اضافه میشود؛ یعنی اگر او غول \(i\) را تسخیر کند، قدرت او به اندازهی \(a_i\) زیاد میشود.
مهسا برای خارج شدن از خانه غولها، باید همه غولها را تسخیر کند. او از آنجایی که برای ورود به بازی، هزینهی بسیار زیادی پرداخته نمیخواهد هزینهی زیادی برای تسخیر غولها بپردازد؛ بنابراین از شما میخواهد که کمترین هزینهی لازم برای تسخیر همه غولها را بدست آورید.
ورودی
در سطر اول ورودی عدد \(n\)، تعداد غولها آمدهاست.
سپس در \(i\) امین سطر از \(n\) سطر بعدی، سه عدد \(a_i\)، \(b_i\) و \(c_i\) آمدهاست که به ترتیب برابر با قدرت غول \(i\)، قدرت لازم برای تسخیر غول \(i\) و هزینهی تسخیر غول \(i\) است.
\[1 \le n \le 2\ 000\] \[0 \le a_i \le b_i \le 2\ 000\] \[1 \le c_i \le 2\ 000\]
خروجی
در تنها سطر خروجی کمترین هزینه لازم برای تسخیر کردن همهی غولها را چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۱ | \(n \le 20\) |
| ۲ | ۱۱ | \(a_i = b_i\) |
| ۳ | ۵۱ | \(n \le 100\) |
| ۴ | ۲۷ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
3
1 2 1
1 3 2
2 2 10
خروجی نمونه ۱
3
ورودی نمونه ۲
4
2 3 4
3 4 5
4 5 6
5 6 7
خروجی نمونه ۲
5