#abc172cL. C - Tsundoku (AI)

C - Tsundoku (AI)

AI翻译,公式、数字等可能存在问题,如果存在问题,请点击上面查看英文版

分数:300300 分

题目描述

我们有两个桌子:A 和 B。桌子上 A 有 NN 本书,桌子上 B 有 MM 本书。

阅读第 ii 本书需要 A_iA\_i 分钟(1≤i≤N1 \leq i \leq N),阅读第 ii 本书需要 B_iB\_i 分钟(1≤i≤M1 \leq i \leq M)。

考虑以下操作:

  • 选择一个还有书的桌子,阅读该桌子上最上面的书,并从桌子上移除它。

我们可以重复执行这个操作,最多花费 KK 分钟的时间,问我们最多可以阅读多少本书?我们忽略除阅读外的任何时间。

约束

  • 1≤N,M≤2000001 \leq N, M \leq 200000

  • 1≤K≤1091 \leq K \leq 10^9

  • 1≤A_i,B_i≤1091 \leq A\_i, B\_i \leq 10^9

  • 输入的所有值都是整数。


输入

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

NN MM KK

A1A_1 A2A_2 …\ldots ANA_N

B1B_1 B2B_2 …\ldots BMB_M

输出

打印一个整数,表示可以阅读的最大书籍数量。


样例输入 1

3 4 240

60 90 120

80 150 80 150

样例输出 1

3

在这个例子中,从顶部开始阅读桌子上 A 的第 11-st、第 22-nd、第 33-rd 本书分别需要 6060、9090、120120 分钟,从顶部开始阅读桌子上 B 的第 11-st、第 22-nd、第 33-rd、第 44-th 本书分别需要 8080、150150、8080、150150 分钟。

我们可以在 230230 分钟内阅读三本书,如下所示,这是我们在 240240 分钟内可以阅读的最大书籍数量。

  • 用 6060 分钟阅读桌子上 A 的最上面的书,并从桌子上移除它。

  • 用 8080 分钟阅读桌子上 B 的最上面的书,并从桌子上移除它。

  • 用 9090 分钟阅读桌子上 A 的最上面的书,并从桌子上移除它。


样例输入 2

3 4 730

60 90 120

80 150 80 150

样例输出 2

7


样例输入 3

5 4 1

1000000000 1000000000 1000000000 1000000000 1000000000

1000000000 1000000000 1000000000 1000000000

样例输出 3

0

注意整数溢出。