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

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