Module: الگوها در برنامه نویسی پویا

Problem

در المپیاد بین منطقه ای برنامه نویسی ربات، مسابقات در یک دور و در قالبی غیر معمول برگزار می شود. تکالیف به صورت متوالی به شرکت‌کنندگان داده می‌شود، نه همه آنها در همان ابتدای دور، و هر یکمین کار (1 ≤ i ≤ n) در زمان خود s_i پس از دریافت کار بعدی، هر شرکت کننده باید بلافاصله تعیین کند که آیا آن را حل خواهد کرد یا خیر. اگر او تصمیم گرفت این مشکل را حل کند، آنگاه t_i دقیقه فرصت دارد تا راه حل آن را برای تأیید ارسال کند و در این مدت نمی تواند به حل مشکل دیگری روی بیاورد. اگر شرکت کننده از حل این مشکل امتناع کند، در آینده نمی تواند به آن بازگردد. در لحظه ای که زمان تعیین شده برای کاری که شرکت کننده در حال حل آن است به پایان رسیده است، می تواند در صورت وجود چنین کاری، شروع به حل کار دیگری کند که در همان لحظه در دسترس قرار گرفته است یا منتظر باشد تا کار دیگری ظاهر شود. در همان زمان، برای حل صحیح مشکل i، شرکت‌کننده امتیاز c_i دریافت می‌کند.

آرتور که نماینده یکی از مراکز هوش مصنوعی منطقه‌ای در المپیاد بین منطقه‌ای است، می‌داند که نه تنها توانایی حل مشکلات، بلکه محاسبه صحیح استراتژیک در مورد اینکه کدام مشکلات باید حل شوند و کدام‌ها را نادیده بگیریم، نقش مهمی در آن بازی می‌کند. چنین المپیادی او، مانند همه شرکت کنندگان، قبل از شروع تور می داند که هر کار در چه مقطع زمانی در دسترس خواهد بود، چقدر زمان برای حل آن اختصاص داده می شود و چند امتیاز می توانید برای حل آن کسب کنید. آرتور دانش آموز با استعدادی است و بنابراین می تواند هر مشکلی را که برای حل آن در المپیاد انتخاب می کند در زمان تعیین شده با موفقیت حل کند و برای تایید قبولی کند.

لازم است برنامه ای بنویسید که حداکثر امتیازی را که آرتور می تواند با انتخاب بهینه مسائلی که حل خواهد کرد و همچنین تعداد و فهرست چنین مسائلی به دست آورد را تعیین کند.

ورودی
خط اول شامل یک عدد صحیح n (1 ≤ n ≤ 10⁵) تعداد مشکلات در المپیاد است.

n سطر بعدی شامل توضیحاتی از مسائل است، سه عدد در هر خط: si لحظه ای که i-مین مسئله بر حسب دقیقه ظاهر می شود، t_i زمان اختصاص داده شده برای حل آن بر حسب دقیقه، و ci چند امتیازاتی که شرکت‌کننده برای حل این مشکل دریافت می‌کند (1 ≤ s_i, t_i, c_i ≤ 109< /sup>).

حصر
خط اول  باید شامل یک عدد واحد باشد – حداکثر امتیازی که آرتور می تواند در المپیاد کسب کند.

خط دوم باید شامل یک عدد صحیح m باشد - تعداد کارهایی که باید با انتخاب بهینه حل شوند.

خط سوم باید حاوی m اعداد صحیح جدا شده با فاصله باشد - اعداد این مسائل به ترتیبی که حل شده اند. کارها به ترتیبی که در فایل ورودی توضیح داده شده اند، از یک شروع می شوند.

اگر چندین پاسخ بهینه وجود دارد، هر یک از آنها را چاپ کنید.

نمونه‌ها

<سر> <بدن>

#	ورودی	خروجی
1	2 1 1 1 2 2 2	3 2 1 2
2	3 1 2 1 3 2 1 2 4 3	3 1 3