At the 2224 All-Russian Olympiad in Informatics, held in Innopolis, delivery is handled by a new generation of robots capable of creating their own clones. Deliveries can be received directly through a window without leaving home.
Initially, there is only one delivery robot. At any moment, the top robot can create one or more new robots directly above itself. This forms a column of robots. The height of each robot is equal to the height of one floor.
During the delivery process, a column of identical robot-clones moves along the dormitory buildings from left to right. The robots' database contains a list of orders, each specifying the window to which it must be delivered. When the column of robots passes a window corresponding to an order, it can perform the delivery if there is a robot in the column located at the level of that window.
While moving, the robot structure may encounter an obstacle. After an obstacle, only those robots that were above the obstacle continue moving. They end up on the ground immediately behind the obstacle, still in the form of a vertical column, and can continue moving, creating new clones, and delivering orders.
The distance between obstacles and windows is sufficiently large, so robots will not pass by a window while crossing an obstacle.
For delivering one order, the delivery company receives $p$ cryptorubles. The cost of creating one new robot is $c$ cryptorubles. The final profit is equal to the total income from delivering orders minus the total cost of creating all robots. The company wants to maximize its profit. It is not required to fulfill all orders, and the robots can stop at any moment and terminate the delivery process.
Determine the maximum profit the company can obtain.
Input
The first line of the input contains four integers $n, m, c, p$ ($0 \le n, m \le 100\,000$, $1 \le c, p \le 10^6$) — the number of obstacles, the number of orders in the database, the cost of creating a robot clone, and the revenue from delivering one order, respectively.
The next $n + m$ lines contain the description of obstacles and windows in the order the robot column encounters them while moving along the buildings from left to right. Each line contains two integers $t_i$ and $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$) — the type of object $t_i$ (1 for an obstacle and 2 for a window) and $h_i$ — the height of the obstacle in floors or the floor number where the window is located.
It is guaranteed that exactly $n$ objects are of type 1, and the remaining $m$ objects are of type 2.
Output
Output a single number — the maximum profit that can be obtained.
Subtasks
| Subtask | Points | Constraints | Required Subtasks |
|---|---|---|---|
| 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$, all obstacle heights are 1 | |
| 6 | 18 | 1 – 5 |
Examples
Input 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Output 1
4
Input 2
1 3 1 5 2 2 2 1 1 9 2 1
Output 2
9
Note
One of the optimal strategies for delivering orders from the first example is shown in the nine figures below; note that fulfilling the second order does not increase the profit.
In the second example, it is sufficient to clone the robot once to deliver the first order, use the resulting robot system to deliver the second order, and it is economically disadvantageous to perform additional cloning to deliver the third order.