题目描述

Nicky is conducting experiments on chemical reactivity. He has prepared $N$ experiments, which are indexed from $0$ to $N - 1$. Now he needs to choose his starting experiment, and then he will conduct all the experiments with indices greater than or equal to that of the chosen one. In other words, if he decides to start from experiment with index $S$, he will run experiments $S, S + 1, \ldots, N - 1$ in this order.

Before the starting experiment, he has a container with a solution. The temperature of the solution is equal to 0 degrees. During the $i$-th experiment ($0 \leq i \leq N - 1$), he performs the following two steps in this order:

1. Changes the temperature of the solution by a given integer number of degrees (it can increase or decrease by an arbitrary amount, or remain the same);
2. Performs an experiment and checks whether a reaction takes place.

It is known that for the $i$-th experiment, the temperature changes by $D_i$ degrees - the temperature increases if $D_i > 0$, decreases if $D_i < 0$, or remains the same if $D_i = 0$. Moreover, the reaction in the $i$-th experiment occurs only if the current temperature (after the change) is greater than or equal to $T_i$. Note that the temperature change from the first step persists regardless of whether the reaction occurs or not.

Nicky wants to have the largest number of reactions occurring so that he can gather as much data as possible. Help him by calculating this number.

Implementation details

You should implement the function reactions:

int reactions(int N, std::vector<int> D, std::vector<long long> T)

• $N$: the number of planned experiments;
• $D$: a vector of $N$ integers, where $D_i$ represents the change in temperature for the $i$-th experiment;
• $T$: a vector of $N$ integers, where $T_i$ represents the minimal temperature of the solution for a reaction to occur during the $i$-th experiment.

This function will be called once for each test. It has to return the maximum number of reactions which can occur if the starting experiment is chosen appropriately.

输入格式

The input format is the following:

• line 1: a single integer - the value of $N$.
• line 2: $N$ integers - $D_0, D_1, \ldots, D_{N-1}$.
• line 3: $N$ integers - $T_0, T_1, \ldots, T_{N-1}$.

输出格式

The output format is the following:

• line 1: one integer - the return value of the call.

5
1 1 -3 1 1
1 3 5 1 2

2

5
1 -3 0 3 2
0 -2 -1 0 3

4

提示

Example 1

Consider the following call:

reactions(5, {1, 1, -3, 1, 1}, {1, 3, 5, 1, 2})

If Nicky chooses to start from experiment with index 3, the temperature of the solution will become 1 which satisfies the constraints for that reaction to take place. During the next experiment the temperature increases to 2 and a reaction occurs again. Since there is no way for more than 2 reactions to occur, the function should return $2$.

Example 2

Consider the following call:

reactions(5, {1, -3, 0, 3, 2}, {0, -2, -1, 0, 3})

The function should return 4 because starting from experiment with index 0 Nicky will observe reactions during the experiments with indices 0, 1, 3 and 4. The temperature starts at 0 degrees and during each experiment the temperature is: $1, -2, -2, 1, 3$.

Constraints

• $1 \leq N \leq 500\,000$
• $-10^9 \leq D_i \leq 10^9$
• $-10^{15} \leq T_i \leq 10^{15}$

Subtasks

Subtask	Points	Required subtasks	Additional constraints
0		-	The examples.
1	15	0	$N \leq 2000$
2			There are at most 20 indices $i$ for which $D_i < 0$.
3	20	-	$D_i \leq 0$ for each $0 \leq i < N$
4		0	The answer is at most 20.
5	30	0 - 4	-