← 返回题目列表

Codeforces · 774/B

B. 重要的杯子

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

Stepan 是一位非常有经验的奥运会参赛者。他获得了 n 杯物理奥林匹克竞赛和 m 杯信息学奥林匹克竞赛冠军。每个杯子都有两个参数:其重要性 ci 和宽度 wi。

Stepan 决定将他的一些杯子暴露在宽度为 d 的架子上,这样:

- 架子上至少有一个物理杯和至少一个信息学杯,
——外露罩杯的总宽度不超过d,
- 从每个科目(物理和信息学)中,一些最重要的杯子被暴露(即,如果某个科目的具有重要性 x 的杯子被暴露,那么该科目的所有具有大于 x 的重要性的杯子也必须被暴露)。

您的任务是考虑上述所有规则,确定当 Stepan 将宽度为 d 的架子上的杯子暴露出来时,Stepan 可以获得的最大可能总显着性。总显着性是所有暴露杯子的显着性之和。

输入

第一行包含三个整数 n、m 和 d (1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 109) — 物理奥赛的杯数、信息学奥赛的杯数和架子的宽度。

以下 n 行中的每一行都包含两个整数 ci 和 wi (1 ≤ ci, wi ≤ 109) — 物理奥林匹克竞赛第 i 个杯子的意义和宽度。

以下 m 行中的每一行包含两个整数 cj 和 wj (1 ≤ cj, wj ≤ 109) — 信息学奥林匹克第 j 杯的意义和宽度。

输出

考虑语句中描述的所有规则,打印最大可能的总显着性,Stepan 可以将宽度为 d 的架子上的杯子暴露出来。

如果没有办法暴露架子上的杯子,则打印 0。

示例

输入 #1

3 1 8
4 2
5 5
4 2
3 2

输出 #1

8

输入 #2

4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4

输出 #2

11

输入 #3

2 2 2
5 3
6 3
4 2
8 1

输出 #3

0

注意

在第一个示例中,Stepan 只有一个信息学杯,必须将其暴露在架子上。它的重要性等于 3,宽度等于 2,因此 Stepan 将其暴露出来后,架子上的可用空间宽度将变为等于 6。此外,Stepan 必须暴露第二个物理杯(其宽度为 5),因为它是物理中最重要的杯子(其重要性等于 5)。此后,Stepan 无法在架子上露出更多杯子,因为没有足够的可用空间。因此,暴露杯子的最大总显着性等于 8。