Bei der gesamtrussischen Informatikolympiade des Jahres 2224, die in Иннополис stattfindet, übernehmen Roboter einer neuen Generation die Lieferungen. Diese Roboter können Klone von sich selbst erzeugen. Eine Lieferung kann direkt durch das Fenster entgegengenommen werden, ohne das Haus zu verlassen.

Anfangs gibt es nur einen Lieferroboter. Zu jedem Zeitpunkt kann der oberste Roboter einen oder mehrere neue Roboter unmittelbar über sich erzeugen. So entsteht eine Säule aus Robotern. Jeder Roboter ist genau so hoch wie ein Stockwerk.

Während der Lieferung bewegt sich die Säule identischer Roboterklone von links nach rechts an den Wohnheimgebäuden entlang. Die Datenbank der Roboter enthält eine Liste der aufgegebenen Bestellungen. Für jede Bestellung ist bekannt, an welches Fenster sie geliefert werden muss. Wenn die Robotersäule an einem Fenster vorbeikommt, zu dem eine Bestellung gehört, kann sie die Lieferung ausführen, sofern sich in der Säule ein Roboter auf der Höhe dieses Fensters befindet.

Während der Bewegung kann die Roboterkonstruktion auf ein Hindernis treffen. Hinter dem Hindernis bewegen sich nur die Roboter weiter, die sich oberhalb des Hindernisses befanden. Sie befinden sich unmittelbar hinter dem Hindernis wieder auf dem Boden, weiterhin als senkrechte Säule, und können sich weiterbewegen, neue Klone erzeugen und Bestellungen ausliefern.

Die Abstände zwischen Hindernissen und Fenstern sind ausreichend groß. Deshalb kommen die Roboter beim Überqueren eines Hindernisses an keinem Fenster vorbei.

Für die Auslieferung einer Bestellung erhält das Unternehmen, das die Lieferung organisiert, $p$ Kryptorubel. Die Erzeugung eines neuen Roboters kostet $c$ Kryptorubel. Der endgültige Gewinn ist die Summe der Einnahmen aus den ausgelieferten Bestellungen abzüglich der Gesamtkosten für die Erzeugung aller Roboter. Das Unternehmen möchte seinen Gewinn maximieren. Dabei muss es nicht alle Bestellungen ausführen, und die Roboter können jederzeit anhalten und den Lieferprozess beenden.

Bestimmen Sie den maximalen Gewinn, den das Unternehmen erzielen kann.

Eingabe

Die erste Zeile der Eingabe enthält vier ganze Zahlen $n,m,c,p$ ($0 \le n,m \le 100000$, $1 \le c,p \le 10^6$): die Anzahl der Hindernisse, die Anzahl der Bestellungen in der Datenbank, die Kosten für die Erzeugung eines Roboterklons und den Erlös aus der Auslieferung einer Bestellung, in dieser Reihenfolge.

Die nächsten $n+m$ Zeilen beschreiben die Hindernisse und die Fenster, an die Bestellungen geliefert werden müssen, in der Reihenfolge, in der die Robotersäule von links nach rechts an den Wohnheimen entlangläuft. Jede Zeile enthält zwei ganze Zahlen $t_i,h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$). Dabei gibt $t_i$ den Objekttyp an ($1$ für ein Hindernis und $2$ für ein Fenster), und $h_i$ ist die Höhe des Hindernisses in Stockwerken beziehungsweise das Stockwerk, in dem sich das Fenster befindet.

Es ist garantiert, dass genau $n$ Objekte den Typ $1$ haben und die übrigen $m$ Objekte den Typ $2$.

Ausgabe

Geben Sie eine Zahl aus: den maximalen Gewinn, der erzielt werden kann.

Teilaufgaben

Beispiele

Eingabe 1

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

Ausgabe 1

4

Eingabe 2

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

Ausgabe 2

9

Hinweis

Eine der optimalen Strategien zur Auslieferung der Bestellungen aus dem ersten Beispiel ist in den folgenden neun Abbildungen dargestellt. Dabei erhöht die Auslieferung der zweiten Bestellung den Gewinn nicht.

Im zweiten Beispiel genügt es, den Roboter einmal zu klonen, um die erste Bestellung auszuliefern, und mit der entstandenen Roboterkonstruktion die zweite Bestellung auszuliefern. Weitere Klone zu erzeugen, um die dritte Bestellung auszuliefern, ist wirtschaftlich nicht vorteilhaft.