问题描述

从 $N$ 种主菜和 $M$ 种副菜中选择菜肴组成一份套餐。主菜只能选择一种，而副菜可以选择任意种类或不选择。同时，每种菜肴最多只能放入套餐一次。

• 第 $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$

• 第一行有三个整数 $N (1 ≤ N ≤ 10,000)$, $M (1 ≤ M ≤ 1,000)$, $L (1 ≤ L ≤ 10,000)$，以空格分隔。
• 接下来 $N$ 行表示主菜的信息。其中，第 $i$ 行表示第 $i$ 种主菜的价格和评分，分别为整数 $A_i (1 ≤ A_i ≤ 10,000)$, $B_i (1 ≤ B_i ≤ 10,000)$。
• 接下来 $M$ 行表示副菜的信息。其中，第 $i$ 行表示第 $i$ 种副菜的价格和评分，分别为整数 $C_i (1 ≤ C_i ≤ 10,000)$, $D_i (1 ≤ D_i ≤ 10,000)$。
• 保证一定能组成套餐。

输出

输出套餐的最大评分，末尾换行。

示例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