AT_cf_2015_relay_g 主菜と副菜

从 $N$ 种主菜和 $M$ 种副菜中选择菜品来组成一份套餐。主菜只能选择 $1$ 种，但副菜可以选择任意多种，也可以一个都不选。每种主菜和副菜在套餐中最多只能选一次。 - 第 $i$ 种主菜的价格为 $A_i$，顾客评分为 $B_i$。 - 第 $i$ 种副菜的价格为 $C_i$，顾客评分为 $D_i$。 套餐的总价格和评分分别为所选主菜和副菜的价格与评分之和。请在套餐总价格不超过 $L$ 的前提下，求套餐评分的最大值。

输入按以下格式从标准输入读入。 > $N$ $M$ $L$ > $A_1$ $B_1$ > $\vdots$ > $A_N$ $B_N$ > $C_1$ $D_1$ > $\vdots$ > $C_M$ $D_M$ - 第 $1$ 行包含三个整数 $N\ (1\leq N\leq 10,000)$，$M\ (1\leq M\leq 1,000)$，$L\ (1\leq L\leq 10,000)$，以空格分隔。 - 接下来的 $N$ 行，每行包含两个整数，表示第 $i$ 种主菜的价格 $A_i\ (1\leq A_i\leq 10,000)$ 和评分 $B_i\ (1\leq B_i\leq 10,000)$。 - 再接下来的 $M$ 行，每行包含两个整数，表示第 $i$ 种副菜的价格 $C_i\ (1\leq C_i\leq 10,000)$ 和评分 $D_i\ (1\leq D_i\leq 10,000)$。 - 保证一定可以组成套餐。

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

由 ChatGPT 4.1 翻译