No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

译自 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$ 是样例。