堆读

题目描述

有两张桌子 A 和 B。桌子 A 上纵向堆着 $N$ 本书,桌子 B 上纵向堆着 $M$ 本书。

桌子 A 上目前从上数第 $i$ 本 $(1 \leq i \leq N)$ 的书读完需要 $A_i$ 分钟,桌子 B 上目前从上数第 $i$ 本 $(1 \leq i \leq M)$ 的书读完需要 $B_i$ 分钟。

考虑以下行为:

• 选择一本还剩下书的桌子,读完该桌子最上面堆着的那本书,并把它从桌子上拿走。

在总用时不超过 $K$ 分钟的前提下反复进行这个行为时,最多能读多少本书?忽略读书以外所需的时间。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

输出格式

输出表示能够读的书的数量最大值的整数。

样例

3 4 240
60 90 120
80 150 80 150

3

这种情况下,桌子 A 从上数第 $1,2,3$ 本书读完分别需要 $60$ 分钟、$90$ 分钟、$120$ 分钟;桌子 B 从上数第 $1,2,3,4$ 本书读完分别需要 $80$ 分钟、$150$ 分钟、$80$ 分钟、$150$ 分钟。

按如下方式可以用 $230$ 分钟读 $3$ 本书,这是在 $240$ 分钟以内能读的书的数量最大值:

• 花 $60$ 分钟读桌子 A 最上面堆着的书,并把它从桌子上拿走。
• 花 $80$ 分钟读桌子 B 最上面堆着的书,并把它从桌子上拿走。
• 花 $90$ 分钟读桌子 A 最上面堆着的书,并把它从桌子上拿走。

3 4 730
60 90 120
80 150 80 150

7

5 4 1
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000

0

请注意整数溢出。

数据范围

• $1 \leq N, M \leq 200000$
• $1 \leq K \leq 10^9$
• $1 \leq A_i, B_i \leq 10^9$
• 输入中的值均为整数。