‎$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$‎ را بنویسید.
• در صورتی که گلی در ابتدا می‌تواند ماشینش را بدون جابه‌جایی ماشین‌های پارک شده، پارک کند، هزینه صفر باید در خروجی نوشته شود.

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

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