题目描述

译自 ROI 2024 Day1 T1. Беспилотная аэрологистика

2224 年，全俄信息学奥林匹克竞赛在因诺波利斯举行，由一群能够克隆自身的新一代机器人负责配送任务。人们可以便捷地通过自家窗户直接接收货物。

初始时，只有一台配送机器人在工作。这台机器人能够在其正上方克隆出若干新机器人，形成一个垂直的机器人纵队，每个机器人的高度恰好与一层楼的高度相等。

在配送过程中，这些机器人会形成一列，沿着宿舍楼从左向右移动。它们的数据库中储存了一个订单列表，每个订单指定了一个具体的窗户作为配送目标。当机器人纵队经过对应的窗户时，列中处于那个高度的机器人就会完成配送。

机器人在移动过程中可能会遇到障碍物。穿过障碍物后，只有那些位于障碍物上方的机器人能继续移动。这些机器人会在障碍物后立即重新排列成垂直列，并能继续前进，同时克隆出新的机器人并处理更多配送订单。

障碍物与窗户之间的距离足够大，确保机器人在穿越障碍物时不会经过任何窗户。

每成功配送一个订单，公司将获得 $p$ 个加密卢布的收入；而克隆一个新机器人则需花费 $c$ 个加密卢布。公司的最终利润是所有配送收入减去所有机器人的创建成本。公司希望最大化其利润，并可以选择不完成全部订单，机器人也可以在任何时候停止配送任务。

任务是确定公司可以实现的最大利润。

输入格式

输入的第一行包含四个整数 $n, m, c, p\, (0 \leq n, m \leq 10^5, 1 \leq c, p \leq 10^6)$，分别表示障碍物的数量、数据库中的订单数量、克隆机器人的成本以及配送一个订单的收入。

在接下来的 $n+m$ 行中，按照机器人纵队从左向右沿宿舍楼移动的顺序，描述了障碍物和需配送订单的窗户。每行包含两个整数 $t_i, h_i\, (1 \leq t_i \leq 2, 1 \leq h_i \leq 10^6)$，其中 $t_i$ 表示对象的类型（$1$ 表示障碍物，$2$ 表示窗户），$h_i$ 表示该对象的高度（按楼层计算）。

系统确保正好有 $n$ 个对象类型为障碍物，其余 $m$ 个对象类型为窗户。

输出格式

输出一个数字，表示可以获得的最大利润值。

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

只需要克隆一次机器人来配送第一个订单，因为这个新克隆的机器人可以继续用来配送第二个订单，而为了第三个订单而进行额外的克隆则在经济上不划算。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。