問題文
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