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

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

اگر یک آنتن با محدوده‌ی پوششی $R$ در نقطه $x$ نصب شود، این آنتن محدوده $[x-R, x+R]$ را پوشش خواهد داد. گوییم یک آنتن یک خانه را پوشش می‌دهد، اگر آنتن سیم‌کارت صاحب‌خانه را پشتیبانی کند و درضمن حداقل یک نقطه از خانه در محدوده‌ی پوششی آنتن باشد.

نصب آنتن برای شرکت‌های MTC1 و MTC2 به ترتیب $C_1$ و $C_2$ تومان هزینه دارد. چون نصب آنتن‌ها برای دو شرکت هزینه سنگینی دارد، این دو شرکت توافق کرده‌اند درصورت کاستن هزینه از آنتن‌های اشتراکی (آنتن‌هایی که هر دو سیم‌کارت را پشتیبانی می‌کند) استفاده کنند. هزینه نصب آنتن اشتراکی $C_3$ تومان است ($\max(C_1,C_2)<C_3 < C_1+C_2$). صرفنظر از نوع آنتن، هر آنتن دارای شعاع پوششی $R$ است.

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

ورودی شامل چندین سناریو است. خط اول هر سناریو شامل 5 عدد صحیح مثبت $n\leq 10^4$ (تعداد خانه‌ها)، $R\leq 10^9$ (شعاع پوششی)، $C_1$ (هزینه نصب آنتن برای شرکت MTC1) و $C_2$ (هزینه نصب آنتن برای شرکت MTC2) و $C_3$ (هزینه نصب آنتن اشتراکی) است. هزینه نصب نابزرگتر از $10^9$ است. در $n$ خط بعد مشخصات خانه‌ها آمده است؛ یک خط برای هر خانه. هر خط با دو عدد صحیح مثبت $a$ و $b$ شروع می‌شود که نشان‌دهنده ابتدا و انتهای خانه است ($0<a \leq b < 10^9$). عدد سوم هر خط نوع سیم‌کارت صاحب‌خانه را مشخص می‌کند. عدد $1$ نشان‌دهنده سیم کارت شرکت MTC1 و عدد $2$ نشان‌دهنده سیم‌کارت شرکت MTC2 است. در این مسئله بازه‌های ورودی ممکن است اشتراک داشته باشند. ورودی با 0 0 0 0 0 خانمه می‌یابد که نیازی به پردازش آن نیست.

برای هر سناریو، هزینه کمینه را در یک خط چاپ کنید.

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

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