באולימפיאדה הכלל־רוסית במדעי המחשב של שנת 2224, המתקיימת ב־Иннополис, המשלוחים מבוצעים באמצעות רובוטים מהדור החדש, המסוגלים ליצור העתקים של עצמם. אפשר לקבל משלוח ישירות דרך החלון, בלי לצאת מהבית.

בתחילה יש רק רובוט משלוחים אחד. בכל רגע הרובוט העליון יכול ליצור רובוט חדש אחד או כמה רובוטים חדשים ישירות מעליו. כך נוצר טור של רובוטים. גובהו של כל רובוט שווה לגובה של קומה אחת.

במהלך המשלוחים, טור של רובוטים משוכפלים זהים נע לאורך בנייני המעונות משמאל לימין. במסד הנתונים של הרובוטים נמצאת רשימת ההזמנות שבוצעו, ולכל הזמנה ידוע החלון שאליו יש למסור אותה. כאשר טור הרובוטים חולף על פני חלון המתאים להזמנה כלשהי, הוא יכול למסור אותה אם יש בטור רובוט בגובה החלון.

במהלך התנועה, מבנה הרובוטים עשוי להיתקל במכשול. לאחר המכשול, רק הרובוטים שנמצאו מעל המכשול ממשיכים לנוע. הם מגיעים לקרקע מיד אחרי המכשול, עדיין בצורת טור אנכי, ויכולים להמשיך לנוע, ליצור העתקים חדשים ולמסור הזמנות.

המרחק בין המכשולים לחלונות גדול מספיק, ולכן בעת המעבר מעל מכשול הרובוטים לא יחלפו על פני חלון.

עבור מסירת הזמנה אחת, החברה המארגנת את המשלוחים מקבלת $p$ קריפטו־רובלים. עלות יצירת רובוט חדש אחד היא $c$ קריפטו־רובלים. הרווח הסופי שווה להכנסה הכוללת ממסירת ההזמנות פחות העלות הכוללת של יצירת כל הרובוטים. החברה רוצה למקסם את הרווח שלה. היא אינה חייבת לבצע את כל ההזמנות, והרובוטים יכולים לעצור בכל רגע ולהפסיק את תהליך המשלוחים.

מצאו את הרווח המרבי שהחברה יכולה להשיג.

קלט

בשורה הראשונה של הקלט נמצאים ארבעה מספרים שלמים $n,m,c,p$ ($0 \le n,m \le 100\,000$, $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$, גובה המכשול בקומות או הקומה שבה נמצא החלון.

מובטח של־$n$ עצמים בדיוק יש סוג $1$, ול־$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

הסבר

אחת האסטרטגיות המיטביות למסירת ההזמנות בדוגמה הראשונה מוצגת בתשעת האיורים שלהלן; ביצוע ההזמנה השנייה אינו מגדיל את הרווח.

בדוגמה השנייה די לשכפל את הרובוט פעם אחת כדי למסור את ההזמנה הראשונה, ולמסור את ההזמנה השנייה באמצעות מערכת הרובוטים שנוצרה. ביצוע שכפול נוסף כדי למסור את ההזמנה השלישית אינו משתלם מבחינה כלכלית.