دو روباه می‌خواهند تعدادی تخم‌مرغ را که یکی یکی از سوراخ وسط سقف می‌افتند بخورند. گرفتن یک تخم‌مرغ تنها در لحظه‌ی رسیدن آن به زمین (و نه بعد و نه قبل از آن) امکان‌پذیر است.

می‌دانیم هضم تخم‌مرغ $0\leq i < n$ توسط روباه $0\leq j \leq 1$، $d_{i.j}$ ثانیه طول کشیده و $e_{i,j}$ واحد انرژی برای آن روباه به ارمغان می‌آورد. اگر روباهی شروع به خوردن تخم‌مرغی بکند، تا پایان مدت لازم برای هضم آن، کار دیگری نمی‌تواند بکند؛ اما بلافاصله بعد از اتمام هضم آن، می‌تواند در همان لحظه خوردن تخم‌مرغ بعدی را آغاز کند. هر تخم‌مرغ حداکثر توسط یک روباه می‌تواند خورده شود و هیچ دو تخم‌مرغی با هم در یک ثانیه به زمین نمی‌رسند. اگر در ثانیه‌ی رسیدن یک تخم‌مرغ به زمین هیچ کدام از دو روباه اقدام به گرفتن آن (و بالطبع خوردن بلافاصله‌اش) نکنند، تخم‌مرغ شکسته شده و برای همیشه از بین می‌رود.

برنامه‌ای بنویسید که:

• زمان رسیدن هر تخم‌مرغ به زمین، مدت زمان هضم آن برای هر روباه و نهایتا جدول کسب انرژی را از ورودی بخواند.
• حداکثر مجموع میزان انرژی دو روباه پس از افتادن تمامی تخم‌مرغ‌ها را محاسبه کند.
• این عدد را در خروجی بنویسید.

سطر نخست وردی شامل عدد$n$، تعداد تخم‌مرغ‌هاست.

در هر یک از $n$ سطر بعدی، اطلاعات مربوط به یک تخم‌مرغ می‌آید این اطلاعات در سطر $i$ام ($0\leq I \leq n$) از چپ به راست عبارت‌اند از زمان افتادن تخم‌مرغ $i$ام ($t_i$)، مدت زمان هضم آن تخم‌مرغ توسط روباه اول ($d_{i,0}$)، انرژی اکتسابی توسط روباه اول پس از خوردن آن ($e_{i,0}$)، مدت زمان هضم آن تخم‌مرغ توسط روباه دوم ($d_{i,1}$) و نهایتا انرژی اکتسابی توسط روباه دوم پس از خوردن آن ($e_{i,1}$).

تمام اعداد ورودی صحیح و مثبت‌اند. $n\leq 4007$ و سایر اعداد کوچک‌تر یا مساوی $10^5$ هستند.

در تنها سطر خروجی، بیشینه‌ی مجموع انرژی دو روباه در پایان کار را بنویسید.

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

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