Tractor

Task

On a field, there are two stacks of hay bales.
The first stack contains $n$ bales, where the first bale is at the bottom, and the $n^{th}$ bale is at the top. The $i^{th}$ bale has weight $a_i$.
The second stack contains $m$ bales, where the first bale is at the bottom, and the $m^{th}$ bale is at the top. The $j^{th}$ bale has weight $b_j$.
You want to transport the $n + m$ bales to the processing plant using a tractor with a total load limit $w$. In one trip, you may load bales from both stacks, but a bale cannot be loaded before the bales on top of it have been loaded. The total weight of the bales loaded into the tractor on each trip must not exceed $w$.

Determine the minimum number of trips required to clear the two stacks.

Input data

The first line contains three integers representing the number of bales from the first stack $n$, the number of bales from the second stack $m$, and the load limit of the tractor $w$.
The second line contains $n$ integers $a_1, \ldots, a_n$.
The third line contains $m$ integers $b_1, \ldots, b_m$.

Output data

The output consists of a single integer representing the minimum number of trips needed to transport all $n + m$ bales.

Constraints and clarifications

• $1 \leq n, m \leq 2\ 000$
• $1 \leq a_i, b_j \leq w \leq 10^9$

Example

stdin

4 5 10
4 3 7 5
3 4 3 6 2

stdout

4

Explanation

The minimum number of trips required to clear the two stacks is $4$; this can be achieved in the following way:

• On the first trip, we take the following from the two stacks: the hay bales with weights $a_4$ and $b_5$ with a total weight of $7$;
• On the second trip, the hay bales with weights $a_3$ and $a_2$ with a total weight of $10$;
• On the third trip, the hay bales with weights $a_1$ and $b_4$ with a total weight of $10$;
• On the fourth trip, the hay bales with weights $b_3, b_2$ and $b_1$ with a total weight of $10$.