You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

小明正在一个热闹非凡的美食节上。这里有两个他最喜欢的小吃摊：摊位 A 和摊位 B。

• 摊位 A 有 $n$ 道菜品，按 $1, 2, \dots, n$ 的顺序排成一列。吃掉第 $i$ 道菜需要 $A_i$ 分钟，并能获得 $A'_i$ 的快乐值。
• 摊位 B 有 $m$ 道菜品，按 $1, 2, \dots, m$ 的顺序排成一列。吃掉第 $i$ 道菜需要 $B_i$ 分钟，并能获得 $B'_i$ 的快乐值。

小明每次只能选择一个摊位，并吃掉该摊位当前排在最前面的菜品。吃完后，这道菜就会从队列中被移除。

小明总共有 $K$ 分钟的用餐时间。他想知道，在不超过总时间 $K$ 的前提下，他最多可以获得多少快乐值？

格式

输入格式

第一行包含三个整数 $n , m, K$，分别表示摊位 A 的菜品数量、摊位 B 的菜品数量和小明的总时间。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示摊位 A 每道菜的耗时。

第三行包含 $n$ 个整数 $A'_1, A'_2, \dots, A'_n$，表示摊位 A 每道菜的快乐值。

第四行包含 $m$ 个整数 $B_1, B_2, \dots, B_m$，表示摊位 B 每道菜的耗时。

第五行包含 $m$ 个整数 $B'_1, B'_2, \dots, B'_m$，表示摊位 B 每道菜的快乐值。

输出格式

输出一个整数，表示在 $K$ 分钟内能获得的最大快乐值。

样例

样例输入 #1

4 5 95
10 20 15 30
12 18 14 25
12 18 22 10 25
15 20 21 11 22

样例输出 #1

97

样例输入 #2

3 3 100
50 10 60
100 -200 110
40 40 40
50 50 50

样例输出 #2

150

样例解释 #2

注意：美味值可能出现负数。

数据规模

对于 $40\%$ 的数据，$1 \leq n , m \leq 10^3$。

对于 $100\%$ 的数据，$1 \leq n ,m \leq 10^5$，$1 \leq K \leq 10^{14}$，$1 \leq A_i ,B_i \leq 10^9$，$-10^9 \leq A'_i,B'_i \leq 10^9$。