رایان درحال گذراندن خدمت سربازی است. در یکی از بخش‌های آموزش‌نظامی او باید با استفاده از اسلحه‌ای خاص به تعدادی هدف شلیک کند. هریک از هدف‌ها در لحظه‌ای مشخص ظاهر می‌شوند و پس از ظاهر شدن در لحظه‌ای دیگر ناپدید می‌شوند. هریک از اهداف، امتیاز مخصوص به خود را دارند و امکان شلیک به یک هدف بیش از یک‌بار وجود دارد، منتها بعد از هر بار شلیک، اسلحه رایان به مدت زمان $L$ ثانیه نیاز دارد تا برای شلیک بعدی آماده شود. بدیهی است که هر زمان که رایان تصمیم به شلیک می‌گیرد تنها می‌تواند به اهدافی شلیک کند که در آن لحظه قابل رؤیت هستند. رایان به دنبال یافتن بیش‌ترین امتیازی است که با داشتن $n$ تیر می‌تواند به‌دست آورد.

چند سناریو مجزا به عنوان ورودی داده می‌شوند. در خط اول هر سناریو، سه عدد $n$ (تعداد تیرهای رایان)، $L$ (مدت زمان آماده‌سازی اسلحه بعد از هر شلیک) و $k$ (تعداد اهداف) آمده‌اند و در هریک از $k$ خط بعدی سه عدد $t_a$ (لحظه ظاهر شدن هدف)، $t_d$ (لحظه ناپدید شدن هدف) و $s$ (امتیاز دریافتی در صورت شلیک به هدف) آمده‌اند که هرکدام مربوط به یکی از اهداف می‌باشند. هریک از اهداف در بازه بسته $[t_a, t_d]$ قابل رؤیت هستند و رایان می‌تواند در لحظه‌های ظاهر شدن و ناپدید شدن اهداف نیز به آن‌ها شلیک کند. فرض کنید تمام اعداد ورودی اعداد صحیح نامنفی هستند و می‌دانیم $n \leq 100$ و $L \leq 10^9$ و برای هر یک از اهداف داریم: $0 \leq t_a < t_d \leq 10^9$. درضمن امتیاز هیچ‌یک از اهداف بیش‌تر از $10^6$ نیست و $k \leq 1000$ می‌باشد. آخرین خط ورودی شامل سه عدد صفر است که نیازی به پردازش آن‌ها نیست.

برای هریک سناریوهای ورودی، در خطی جداگانه بیش‌ترین امتیازی که رایان می‌تواند به‌دست آورد را چاپ کنید.

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

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