Background

Translated from ROI 2024 D1T1。

When ROI 2224 was held, a group of robots that can clone themselves were responsible for deliveries. People did not need to go outside and could receive packages directly through their windows.

At the beginning, there is only one delivery robot. At any time, the topmost robot can clone one or more new robots above itself, forming a “robot stack”. The height of each robot is equal to one floor.

During delivery, the robot stack moves from left to right along the dormitory building. The robots’ database contains a list of orders, and each order specifies a window that needs a delivery. When the robot queue passes a window, if there is a robot at the same height as that window, the delivery can be completed immediately.

While moving, the robot stack may hit obstacles. After hitting an obstacle, only the robots above the obstacle’s height can continue moving. After passing the obstacle, these robots immediately regroup into a robot stack, and can continue moving, cloning, and completing deliveries.

The distance between obstacles and windows is large enough, so when the robots pass an obstacle, they will not pass a window at the same time.

Problem Description

For each completed order, the robot company earns $p$ units of virtual currency, and the cost to clone one new robot is $c$ units of virtual currency. The final profit equals the total income from delivered orders minus the total cost of all robot cloning. The company wants to maximize the profit. Determine the maximum profit the company can obtain.

The company does not have to complete all orders, and the robots may stop delivering at any time.

Input Format

The first line contains four integers $n, m, c, p$ ($0 \le n, m \le 100000$, $1 \le c, p \le 1000000$), representing the number of obstacles, the number of orders, the cost to clone one robot, and the income for delivering each order, respectively.

The next $n + m$ lines describe the obstacles and windows in detail, given in left-to-right order. Each line contains two integers $t_i$ and $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 1000000$), where $t_i$ indicates the type of the object ($1$ for an obstacle, $2$ for a window), and $h_i$ indicates the height of the obstacle or the floor of the window.

It is guaranteed that there are $n$ obstacles, and the remaining $m$ objects are windows.

Output Format

Output one integer, the maximum profit that can be obtained.

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

4

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

9

Hint

Explanation for sample $1$:

Below is one of the best strategies for delivering orders. If you choose to deliver to the second window, it will not increase the company’s profit.

Explanation for sample $2$:

You only need to clone a robot once to deliver to the first window, because this newly cloned robot can continue to deliver to the second window. Additional cloning to deliver to the third window is not cost-effective.

Below is the table of scores and special properties for each subtask. For the full Constraints, see the input format.

Translated by ChatGPT 5