Podczas ogólnorosyjskiej olimpiady informatycznej w roku 2224, odbywającej się w Иннополис, dostawami zajmują się roboty nowej generacji, które potrafią tworzyć swoje klony. Dostawę można odebrać bezpośrednio przez okno, nie wychodząc z domu.
Początkowo istnieje tylko jeden robot dostawczy. W dowolnym momencie najwyżej znajdujący się robot może utworzyć jednego lub kilku nowych robotów bezpośrednio nad sobą. W ten sposób powstaje kolumna robotów. Wysokość każdego robota jest równa wysokości jednego piętra.
Podczas dostarczania zamówień kolumna identycznych robotów-klonów przemieszcza się wzdłuż budynków akademików od lewej do prawej. W bazie danych robotów znajduje się lista złożonych zamówień; dla każdego z nich wiadomo, do którego okna należy je dostarczyć. Gdy kolumna robotów mija okno odpowiadające któremuś zamówieniu, może je dostarczyć, jeśli w kolumnie znajduje się robot na wysokości tego okna.
Podczas przemieszczania się konstrukcja z robotów może natrafić na przeszkodę. Za przeszkodą ruch kontynuują jedynie te roboty, które znajdowały się ponad nią. Trafiają one na ziemię bezpośrednio za przeszkodą, nadal tworząc pionową kolumnę, i mogą dalej się przemieszczać, tworzyć nowe klony i dostarczać zamówienia.
Odległość między przeszkodami a oknami jest wystarczająco duża, dlatego podczas pokonywania przeszkody roboty nie mijają żadnego okna.
Za dostarczenie jednego zamówienia firma organizująca dostawy otrzymuje $p$ kryptorubli. Koszt utworzenia jednego nowego robota wynosi $c$ kryptorubli. Końcowy zysk jest równy łącznemu przychodowi z dostaw pomniejszonemu o łączny koszt utworzenia wszystkich robotów. Firma chce zmaksymalizować swój zysk. Nie musi przy tym zrealizować wszystkich zamówień, a roboty mogą w dowolnym momencie się zatrzymać i zakończyć dostawy.
Wyznacz maksymalny zysk, jaki może osiągnąć firma.
Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite $n$, $m$, $c$, $p$ ($0 \le n,m \le 100\,000$, $1 \le c,p \le 10^6$): odpowiednio liczba przeszkód, liczba zamówień w bazie, koszt utworzenia klona robota oraz opłata za dostarczenie jednego zamówienia.
Kolejne $n+m$ wierszy opisuje przeszkody i okna, do których trzeba dostarczyć zamówienia, w kolejności, w jakiej kolumna robotów napotyka je, przemieszczając się wzdłuż akademików od lewej do prawej. Każdy wiersz zawiera dwie liczby całkowite $t_i$ i $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$): typ obiektu $t_i$ ($1$ oznacza przeszkodę, a $2$ okno) oraz $h_i$, czyli wysokość przeszkody wyrażoną w piętrach lub piętro, na którym znajduje się okno.
Gwarantowane jest, że dokładnie $n$ obiektów ma typ $1$, a pozostałe $m$ obiektów ma typ $2$.
Wyjście
Wypisz jedną liczbę: największy zysk, jaki można osiągnąć.
Podzadania
| Podzadanie | Punkty | Ograniczenia: $n$ | Ograniczenia: $m$ | Dodatkowe ograniczenia | Wymagane podzadania |
|---|---|---|---|---|---|
| $1$ | $24$ | $n \le 100$ | $m \le 100$ | $h_i \le 100$ | |
| $2$ | $12$ | $n=0$ | |||
| $3$ | $14$ | $n=1$ | |||
| $4$ | $15$ | $m=1$ | |||
| $5$ | $17$ | $c=1$, $p=10^6$; wysokości wszystkich przeszkód są równe $1$ | |||
| $6$ | $18$ | Przykład, $1$–$5$ |
Przykład
Wejście 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Wyjście 1
4
Wejście 2
1 3 1 5 2 2 2 1 1 9 2 1
Wyjście 2
9
Uwagi
Jedna z optymalnych strategii dostarczania zamówień z pierwszego przykładu została przedstawiona na dziewięciu poniższych rysunkach. Zrealizowanie drugiego zamówienia nie zwiększa zysku.
W drugim przykładzie wystarczy raz sklonować robota, aby dostarczyć pierwsze zamówienie, a następnie przy pomocy powstałej kolumny robotów dostarczyć drugie zamówienie. Dodatkowe klonowanie w celu dostarczenia trzeciego zamówienia jest nieopłacalne.