P5918. 落选加价成交额

场次：2026年10月14日-非AI方向 · 来源：CodeFun2000 P5918

题目描述

证券交易所里，买进与卖出两方递出的委托单，要依照开价高低和递单早晚完成配对，配上了才记入成交。本所执行的配对办法如下：

1. 买方配对办法： 买方委托单按递出的先后，逐笔进入配对。选中的卖方，开价不得超过这位买方的出价，而且要和该出价隔得最近。倘若卖方开价全部高于这位买方的出价，这位买方的委托单就先跳过。
2. 卖方权益： 若仍有开价比本笔成交价更便宜的卖方委托单，只因隔得更远而本轮未被挑中，这些未被挑中的低开价卖方委托单可以把开价上调，每错过一轮上调 $w$ 元。
3. 配对数量： 双方按手数更少的一边成交，尚未配对的剩余手数留到后一轮继续（后一轮一样要执行上面第 $2$ 条）。

请根据所给的卖方委托单与买方委托单，求出最终计入的成交额：每笔配对成功的「开价乘以手数」全部累加。

补充说明： 卖方权益还有一类错过但不许上调的情形——两笔卖方开价相同，没被挑中的那笔同价卖方委托单不许上调。多笔开价并列且都是当前最高时，取更早递出的那一笔。

输入格式

数据经由标准输入进入程序。

• 首行给出整数 $w$（$0 \le w \le 10^9$），表示每错过一轮的上调幅度。
• 次行给出整数 $a$（$0 \le a \le 10^4$），表示卖方委托单有多少笔。
• 其后 $a$ 行，一行写两个整数，依次是这笔卖方委托单的开价与手数。
• 然后一行给出整数 $b$（$0 \le b \le 10^4$），表示买方委托单有多少笔。
• 其后 $b$ 行，一行写两个整数，依次是这笔买方委托单的开价与手数。

开价和手数都位于区间 $[1, 10^9]$。

输出格式

• 打印一个整数，即最终计入的成交额，也就是每笔配对成功的「开价乘以手数」之和。

示例

示例 1

输入：

5
3
6 2
6 1
2 1
1
15 4

输出：

30

说明：

• 卖方甲：开价 $6$，手数 $2$
• 卖方乙：开价 $6$，手数 $1$
• 卖方丙：开价 $2$，手数 $1$
• 买方：出价 $15$，手数 $4$，上调幅度 $5$

配对过程：

• 第 $1$ 轮： 甲、乙开价都是 $6$，取更早的甲。成交价 $6$，成交 $2$ 手。乙同价不上调，丙上调到 $7$
• 第 $2$ 轮： 乙隔了 $9$，丙隔了 $8$，丙更近，成交价 $7$。乙上调到 $11$
• 第 $3$ 轮： 乙开价 $11$，成交价 $11$
• 合计： $6 \times 2 + 7 + 11 = 30$

示例 2

输入：

2
4
5 4
9 2
14 1
30 1
3
8 3
16 1
12 4

输出：

60

说明：

1. 出价 $8$、手数 $3$ 的买方，配上开价 $5$、手数 $4$ 的卖方，成交 $3$ 手，开价 $5$，金额 $15$。该卖方还剩 $1$ 手，没有更便宜的开价需要上调。
2. 出价 $16$、手数 $1$ 的买方，配上开价 $14$ 的卖方，成交 $1$ 手，金额 $14$。开价 $5$ 与 $9$ 都低于 $14$，各上调 $2$，变成 $7$ 与 $11$。
3. 出价 $12$、手数 $4$ 的买方，先配开价 $11$、手数 $2$ 的卖方，成交 $2$ 手，金额 $22$。开价 $7$ 再上调 $2$，变成 $9$。
4. 该买方还剩 $1$ 手，再配开价 $9$ 的剩余 $1$ 手，成交价 $9$，金额 $9$。开价 $30$ 高于出价，配不上。

合计 $15 + 14 + 22 + 9 = 60$。