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。