← 返回题目列表

Codeforces · 1320/C

C. 暗筏世界:阿撒托斯之战

中文机器翻译题面 查看原题

Roma 正在玩他最喜欢的游戏 World of Darkraft 的新扩展包。他创造了一个新角色,并正在进行他的第一次磨练。

罗马可以选择购买 $$$n$$$ 不同武器中的一套,以及 $$$m$$$ 不同盔甲套装中的一套。武器 $$$i$$$ 具有攻击修正 $$$a_i$$$,价值 $$$ca_i$$$ 金币,盔甲套装 $$$j$$$ 具有防御修正 $$$b_j$$$,价值 $$$cb_j$$$ 金币。

选择装备后,罗马可以继续击败一些怪物。他可以尝试击败许多 $$$p$$$ 怪物。怪物$$$k$$$具有防御$$$x_k$$$,攻击$$$y_k$$$并拥有$$$z_k$$$金币。如果罗马的武器攻击调整值大于怪物的防御力,并且他的护甲套装的防御调整值大于怪物的攻击力,则罗马可以击败怪物。也就是说,如果 $$$a_i > x_k$$$ 且 $$$b_j > y_k$$$,则可以使用武器 $$$i$$$ 和盔甲套装 $$$j$$$ 击败怪物 $$$k$$$。击败怪物后,罗马夺走了他们身上所有的硬币。在磨练过程中,罗马可以击败任意数量的怪物。怪物不会重生,因此每个怪物最多只能击败一个。

由于罗马的过度捐赠,我们可以假设他拥有无限数量的游戏货币,并且可以购买任何武器和盔甲套装。尽管如此,他还是希望将磨练的利润最大化。利润的定义是从所有击败的怪物身上获得的总金币减去他的装备成本。请注意,罗马必须购买武器和盔甲套装,即使他无法用获得的硬币支付其费用。

帮助罗马找到研磨的最大利润。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$p$$$ ($$$1 \leq n, m, p \leq 2 \cdot 10^5$$$)——分别是可用武器、盔甲套装和怪物的数量。

以下 $$$n$$$ 行描述了可用的武器。这些行的第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$ca_i$$$ ($$$1 \leq a_i \leq 10^6$$$, $$$1 \leq ca_i \leq 10^9$$$) — 攻击修正值和武器 $$$i$$$ 的成本。

以下 $$$m$$$ 行描述了可用的盔甲套装。这些行的第 $$$j$$$ 包含两个整数 $$$b_j$$$ 和 $$$cb_j$$$ ($$$1 \leq b_j \leq 10^6$$$, $$$1 \leq cb_j \leq 10^9$$$) - 防御修正值和盔甲套装 $$$j$$$ 的成本。

以下 $$$p$$$ 行描述了怪物。这些行的第 $$$k$$$ 包含三个整数 $$$x_k, y_k, z_k$$$ ($$$1 \leq x_k, y_k \leq 10^6$$$, $$$1 \leq z_k \leq 10^3$$$) — 怪物 $$$k$$$ 的防御力、攻击力和金币数量。

输出

打印一个整数——研磨的最大利润。

示例

输入 #1

2 3 3
2 3
4 7
2 4
3 2
5 11
1 2 4
2 1 6
3 4 6

输出 #1

1