/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
二台の机 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 分を超えないようにこの行為を繰り返すとき、最大で何冊の本を読むことができるでしょうか。本を読むこと以外に要する時間は無視します。
制約
- 1 \leq N, M \leq 200000
- 1 \leq K \leq 10^9
- 1 \leq A_i, B_i \leq 10^9
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
読むことのできる本の最大数を表す整数を出力せよ。
入力例 1
3 4 240 60 90 120 80 150 80 150
出力例 1
3
この場合、机 A の上から 1,2,3 番目の本はそれぞれ読むのに 60 分、90 分、120 分を要し、机 B の上から 1,2,3,4 番目の本はそれぞれ読むのに 80 分、150 分、80 分、150 分を要します。
以下のようにすることで 230 分で 3 冊の本を読むことができ、これが 240 分以内に読むことのできる本の最大数です。
- 机 A の最も上に積まれている本を 60 分かけて読み、この本を机から取り除く。
- 机 B の最も上に積まれている本を 80 分かけて読み、この本を机から取り除く。
- 机 A の最も上に積まれている本を 90 分かけて読み、この本を机から取り除く。
入力例 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
整数のオーバーフローに注意してください。
Score : 300 points
Problem Statement
We have two desks: A and B. Desk A has a vertical stack of N books on it, and Desk B similarly has M books on it.
It takes us A_i minutes to read the i-th book from the top on Desk A (1 \leq i \leq N), and B_i minutes to read the i-th book from the top on Desk B (1 \leq i \leq M).
Consider the following action:
- Choose a desk with a book remaining, read the topmost book on that desk, and remove it from the desk.
How many books can we read at most by repeating this action so that it takes us at most K minutes in total? We ignore the time it takes to do anything other than reading.
Constraints
- 1 \leq N, M \leq 200000
- 1 \leq K \leq 10^9
- 1 \leq A_i, B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
Print an integer representing the maximum number of books that can be read.
Sample Input 1
3 4 240 60 90 120 80 150 80 150
Sample Output 1
3
In this case, it takes us 60, 90, 120 minutes to read the 1-st, 2-nd, 3-rd books from the top on Desk A, and 80, 150, 80, 150 minutes to read the 1-st, 2-nd, 3-rd, 4-th books from the top on Desk B, respectively.
We can read three books in 230 minutes, as shown below, and this is the maximum number of books we can read within 240 minutes.
- Read the topmost book on Desk A in 60 minutes, and remove that book from the desk.
- Read the topmost book on Desk B in 80 minutes, and remove that book from the desk.
- Read the topmost book on Desk A in 90 minutes, and remove that book from the desk.
Sample Input 2
3 4 730 60 90 120 80 150 80 150
Sample Output 2
7
Sample Input 3
5 4 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
0
Watch out for integer overflows.