====== ParkIt ====== ‎$n$‎ ماشین در حاشیه‌ی یک سمت خیابان گلبرگ، پشت سر هم پارک شده‌اند. یک روز عصر، گلی - که یکی از ساکنان خیابان گلبرگ است - وارد این خیابان شده و متوجه می‌شود که جای پارک برای ماشینش وجود ندارد‎!‎ به‌عبارت دقیق‌تر، اگر فرض کنیم ماشین شماره ‎$i$‎ (که ‎$1\le i \le n$‎) از نقطه‌ی ‎$a_i$ (از ابتدای خیابان) تا نقطه‌ی ‎$b_i$‎ را اشغال کرده‌است، طول خیابان ‎$D$‎ و طول ماشین گلی ‎$L$‎ است، در این صورت فاصله‌ی هر دو ماشینی که در خیابان پشت سر هم پارک شده‌اند )‎ و فاصله‌ی قبل از اولین ماشین در خیابان همگی کمتر از ‎$L$‎ هستند. با کمی دقت، گلی در می‌یابد که بین بعضی از ماشین‌ها فاصله خالی وجود دارد. به‌عنوان مثال اگر ‎$[a_1,b_1] = [18,22]$‎، ‎$[a_2,b_2] = [29,37]$‎، ‎$[a_3,b_3] = [1,16]$‎، ‎$[a_4,b_4] = [22,26]$‎ و طول خیابان ‎$D=37$‎ باشد، در این‌صورت بین ماشین شماره سه و یک، به‌اندازه‌ی ‎۲‎ واحد فاصله‌ی خالی (از ‎۱۶‎ تا ۱۸)‎ و بین ماشین شماره چهار و دو، ‎۳‎ فاصله‌ی خالی وجود دارد، اما ماشین شماره یک و چهار به‌هم چسبیده‌اند. در این حال و هوا، ایده‌ای که به ذهن گلی می‌رسد این‌ست که اگر تعدادی از ماشین‌ها به‌سمت جلو یا عقب بروند در این‌صورت یک جای خالی مناسب (به‌طول حداقل ‎$L$)‎ برای او پیدا می‌شود. مثلاً در مثال گفته شده در بالا، اگر ‎$L=5$‎ باشد، کافی‌ست ماشین‌های شماره یک و چهار هر دو، ‎۳‎ واحد به سمت جلو حرکت کنند تا بین ماشین شماره سه و ماشین شماره یک فاصله برابر ‎۵‎ ایجاد شده و گلی بتواند ماشینش را پارک کند. واضح‌ست که در برخی مواقع شاید لازم باشد تعداد بیش‌تری از ماشین‌ها جابه‌جا شده و از آن میان، عده‌ای به عقب و عده‌ای به جلو بروند. ترتیب عقب و جلو رفتن، دلخواه است؛ منتهی ترتیب داخلی ماشین‌ها باید ثابت بماند. با تجربه‌ی قبلی‌ای که گلی از اهالی خیابان گلبرگ دارد، می‌داند که برای این‌که ماشین ‎$i$،‎اُم به‌اندازه‌ی ‎$\Delta_i$‎ واحد حرکت کند، باید به صاحب آن به اندازه‌ی ‎$S_i‎ + ‎\Delta_i \times M_i$‎ تومان پول بدهد‎!‎ به‌عنوان مثال ‎$S_5 = 100$‎ و ‎$M_5 = 10$‎ بدین معنی است که مالک ماشین پنجم، برای این‌که ماشینش تکان بخورد ابتدا ‎۱۰۰‎ تومان گرفته و بعد به‌ازای هر یک واحدی که ماشینش عقب یا جلو برود ‎۱۰‎ تومان دیگر هم می‌گیرد‎!‎ در این اوضاع آشفته، گلی از شما که یک برنامه‌نویس هستید کمک می‌خواهد... برنامه‌ای بنویسید که * از ورودی‎ تعداد ماشین‌ها ‎($n$)‎، طول خیابان ‎($D$)‎ و طول ماشین گلی ‎($L$)‎ را بخواند. * برای هر ماشین ‎$i$ (که ‎$1 \le i \le n$)‎، مکان‌های ‎$a_i$‎ و ‎$b_i$‎ و مقادیر ‎$S_i$‎ و ‎$M_i$‎ را بخواند. * کم‌ترین هزینه‌ای که لازم است گلی به اهالی خیابان گلبرگ بپردازد تا بتواند ماشینش را پارک کند، بیابد. * این هزینه را در ‎خروجی‎ بنویسد. ===== ورودی ===== * در سطر اول ورودی، ابتدا عدد ‎$D$‎ و سپس عدد ‎$L$‎ قرار دارد‎.‎ * در سطر دوم ورودی، عدد ‎$n$‎ قرار دارد‎. * در سطر سوم تا ‎$(n+2)$\،‎اُم ورودی در هر خط چهار عدد نوشته می‌شود که این اعداد، ‎$a_i~b_i~S_i~M_i$‎ هستند. * برای تمامی ماشین‌های پارک شده ‎$0 \le a_i < b_i \le D \le 10^7$‎. هیچ دو ماشینی با هم تداخل ندارند. * $M_i$‎ ها و ‎$S_i$‎ ها صحیح، نامنفی و کمتر از ‎$1000$‎ هستند. * ‎$L$‎ همواره مثبت و کمتر از ‎$10^6$‎ است. * ‎$0 \le n \le 5000$‎. * در حداقل ‎۴۰‎ درصد تست‌ها تمامی اعداد ورودی الزاماً کمتر از ‎$1000$‎ می‌باشند. ===== خروجی ===== * در تنها سطر خروجی، کمترین هزینه‌ای که گلی باید پرداخت کند را بنویسید. * در صورتی که گلی هرگز نمی‌تواند ماشینش را در این خیابان پارک کند، در خروجی ‎$-1$‎ را بنویسید. * در صورتی که گلی در ابتدا می‌تواند ماشینش را بدون جابه‌جایی ماشین‌های پارک شده، پارک کند، هزینه صفر باید در خروجی نوشته شود. ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |37 5‎ \\ 4‎ \\ 18 22 10 1‎ \\ 29 37 1 10‎ \\ 1 16 0 1‎ \\ 22 26 10 1 | 24 | * [[سوال ۹|سوال بعد]] * [[سوال ۷|سوال قبل]]