# Tractor

Time limit: 0.1s Memory limit: 256MB Input: Output:

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$
# Points Constraints
1 2 $a_1 = a_2 = \dots = a_n = b_1 = b_2 = \dots = b_m$
2 3 $a_1 = a_2 = \dots = a_n = 1$
3 7 $n, m \leq 7$
4 21 $n, m \leq 50$
5 30 $n, m \leq 500$
6 37 No further constraints

## 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$.