Winter Sales

Winter is beginning and Giorgio's shop has some unsold items left in its warehouses, which will now be put on sale.

The items are arranged in $N$ boxes, numbered from $0$ to $N - 1$, stacked one on top of the other, each with a weight $W_i$. Box $0$ is the topmost box.

A box can only be removed if all the boxes above it have already been removed.

Giorgio must completely empty his warehouse and to do so he has $M$ carts numbered from $0$ to $M - 1$.

The $j$-th cart can move a maximum of $K_j$ boxes and the total weight of the boxes transported cannot exceed $T_j$.

On each trip, Giorgio chooses one of his carts, goes to the warehouse and loads the boxes from the top, respecting the cart's limits. He then returns to the shop and unloads the boxes.

Next, if there are still boxes left, he repeats the operation, choosing whether to change carts or use the same one.

Task

Help Giorgio plan his day by calculating the minimum number of trips he will need to make to empty the warehouse.

Input data

The input file consists of:

• a line containing integer $N$.
• a line containing the $N$ integers $W_{0}, \, \ldots, \, W_{N-1}$.
• a line containing integer $M$.
• a line containing the $M$ integers $K_{0}, \, \ldots, \, K_{M-1}$.
• a line containing the $M$ integers $T_{0}, \, \ldots, \, T_{M-1}$.

Output data

The output file must contain a single line consisting of integer $S$, the answer to the problem.

Constraints and clarifications

• $1 \leq N, M \leq 200 \ 000$.
• $0 \leq W_i \leq 10 \ 000$ for each $i=0\ldots N-1$.
• $0 \leq K_i \leq N$ for each $i=0\ldots M-1$.
• $0 \leq T_i \leq 10^9$ for each $i=0\ldots M-1$.
• It is always possible to remove all boxes from the warehouse.

Example 1

stdin

3
10 10 30
3
3 1 1
25 35 20

stdout

2

Explanation

In the first sample case Giorgio can use the first cart for the first two boxes and the second cart for the last box, so he needs two trips.

Example 2

stdin

5
1 1 1 1 1
2
2 5
5 2

stdout

3

Explanation

In the second sample case Giorgio needs three trips regardless of which cart he chooses.