← 返回题目列表

AtCoder · cf_2015_relay_g

G. 主菜和配菜

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

問題文

N 种类的主菜和 M 从各种副菜中选择料理来组成套餐。主菜有 1 您只能选择一种,但您可以选择任意数量的配菜。 还有配菜 1 您不必选择任何一个。 主菜和配菜都可以包含在课程中。 1 对于每种类型 1 就是这样。

  • i 主菜价格为 A_i 客户评论 B_i 。
  • i 配菜的价格是 C_i 客户评论 D_i 。

整道菜的价格和评分由主菜和配菜的总和决定。 课程价格 L 如果您执行以下操作,请找到课程的最高评分。 在


入力

输入将以以下格式从标准输入提供。

N M L
A_1 B_1
:
A_N B_N
C_1 D_1
:
C_M D_M
  • 1 第几行包含,3 整数 N (1 ≦ N ≦ 10,000), M (1 ≦ M ≦ 1,000), L (1 ≦ L ≦ 10,000) 用空格分隔。
  • 2 从线 N 行中,给出了有关主菜的信息。其中 一个整数,表示第 i (1 ≦ i ≦ N) 第几行包含,i 个主菜的价格和评分 在 A_i (1 ≦ A_i ≦ 10,000), B_i (1 ≦ B_i ≦ 10,000) 。 来自行
  • N+2 从线 M 行中,给出了有关配菜的信息。其中 一个整数,表示第 i (1 ≦ i ≦ M) 第几行包含,i 个配菜的价格和评级 C_i (1 ≦ C_i ≦ 10,000), D_i (1 ≦ D_i ≦ 10,000) 。 来自行
  • 您保证能够创建课程。

出力

最高课程评分 1 行输出。在输出末尾插入换行符。


入力例1

2 2 10
2 3
3 6
3 5
5 5

出力例1

13

入力例2

3 3 10
1 1
2 3
3 5
4 8
5 10
6 12

出力例2

19

入力例3

3 3 10
1 1
11 11
11 11
11 11
11 11
11 11

出力例3

1