في الأولمبياد الروسي للمعلوماتية لعام 2224، الذي يُقام في Иннополис، تتولى التوصيل روبوتات من جيل جديد تستطيع إنشاء نسخ من نفسها. يمكن استلام الطلب مباشرة عبر النافذة دون مغادرة المنزل.

في البداية يوجد روبوت توصيل واحد فقط. يستطيع الروبوت الموجود في أعلى العمود، في أي لحظة، إنشاء روبوت جديد واحد أو عدة روبوتات جديدة مباشرة فوقه. وهكذا يتكوّن عمود من الروبوتات. يساوي ارتفاع كل روبوت ارتفاع طابق واحد.

أثناء التوصيل يتحرك عمود من الروبوتات المستنسخة المتطابقة بمحاذاة مباني السكن الجامعي من اليسار إلى اليمين. تحتوي قاعدة بيانات الروبوتات على قائمة بالطلبات، وتُعرف لكل طلب النافذة التي يجب توصيله إليها. عندما يمر العمود بجانب نافذة تخص طلبًا، يستطيع توصيله إذا كان في العمود روبوت يقع على مستوى تلك النافذة.

قد يصطدم عمود الروبوتات بعائق أثناء تحركه. لا يواصل الحركة بعد العائق إلا الروبوتات التي كانت أعلى من العائق. تستقر هذه الروبوتات على الأرض مباشرة خلف العائق، وتظل على شكل عمود رأسي، ويمكنها مواصلة الحركة وإنشاء نسخ جديدة وتوصيل الطلبات.

المسافة بين العوائق والنوافذ كبيرة بما يكفي، ولذلك لن تمر الروبوتات بجانب أي نافذة أثناء عبور عائق.

تحصل الشركة المنظمة للتوصيل على $p$ روبل مشفّر مقابل توصيل طلب واحد. تكلفة إنشاء روبوت جديد واحد هي $c$ روبل مشفّر. الربح النهائي يساوي مجموع إيرادات توصيل الطلبات مطروحًا منه مجموع تكلفة إنشاء جميع الروبوتات. تريد الشركة تعظيم ربحها. وهي غير ملزمة بتنفيذ جميع الطلبات، ويمكن للروبوتات أن تتوقف في أي لحظة وتنهي عملية التوصيل.

حدد أقصى ربح يمكن أن تحققه الشركة.

الإدخال

يحتوي السطر الأول على أربعة أعداد صحيحة $n,m,c,p$ ($0\le n,m\le 100000$، $1\le c,p\le 10^6$): عدد العوائق، وعدد الطلبات في قاعدة البيانات، وتكلفة إنشاء نسخة من الروبوت، وسعر توصيل طلب واحد، على الترتيب.

تصف الأسطر التالية وعددها $n+m$ العوائق والنوافذ التي يجب توصيل الطلبات إليها، بترتيب مرور عمود الروبوتات بمحاذاة مباني السكن من اليسار إلى اليمين. يحتوي كل سطر على عددين صحيحين $t_i,h_i$ ($1\le t_i\le 2$، $1\le h_i\le 10^6$): نوع العنصر $t_i$ ($1$ للعائق و$2$ للنافذة)، و$h_i$ الذي يمثل ارتفاع العائق بوحدة الطوابق أو رقم الطابق الذي تقع فيه النافذة.

يُضمن أن عدد العناصر من النوع $1$ هو بالضبط $n$، وأن العناصر المتبقية وعددها $m$ من النوع $2$.

الإخراج

اطبع عددًا واحدًا: أقصى ربح يمكن تحقيقه.

المهام الفرعية

أمثلة

الإدخال 1

2 3 2 6
1 2
2 3
1 1
2 6
2 2

الإخراج 1

4

الإدخال 2

1 3 1 5
2 2
2 1
1 9
2 1

الإخراج 2

9

ملاحظة

توضح الرسومات التسعة أدناه إحدى الاستراتيجيات المثلى لتوصيل الطلبات في المثال الأول؛ ولا يؤدي تنفيذ الطلب الثاني إلى زيادة الربح.

في المثال الثاني يكفي استنساخ الروبوت مرة واحدة لتوصيل الطلب الأول، ثم استخدام مجموعة الروبوتات الناتجة لتوصيل الطلب الثاني. أما إجراء استنساخ إضافي لتوصيل الطلب الثالث فليس مجديًا اقتصاديًا.