Froggy the frog is playing a jumping game. In the game, there are $$$1$$$ starting platform, followed by $$$N$$$ jumping platforms, numbered from $$$1$$$ to $$$N$$$, arranged in a line. The starting platform is $$$1$$$ block wide and the $$$i$$$-th jumping platform is $$$A_i$$$ blocks wide, where $$$A_i$$$ is always an odd number. For each jumping platform, the exact middle block, which is the $$$\lceil \frac{A_i}{2} \rceil$$$-th block, is a scoring block. The distance between the starting platform and the $$$1$$$-st jumping platform is $$$D_1$$$ blocks, and the distance between the $$$(i - 1)$$$-th jumping platform and the $$$i$$$-th jumping platform is $$$D_i$$$ blocks for $$$2 \le i \le N$$$.
Figure 1: An example where $$$N = 3$$$, $$$A = [3, 5, 1]$$$ and $$$D = [1, 3, 2]$$$. The starting platform is green, and the scoring blocks are red.
Froggy starts by standing on the starting platform, and his goal is to reach the $$$N$$$-th jumping platform by performing exactly $$$N$$$ jumps, landing on each platform exactly once. If he successfully lands all $$$N$$$ jumps, he completes the game. Additionally, he can jump at most $$$K_i$$$ blocks for his $$$i$$$-th jump.
Figure 2: For $$$K = [4, 10, 3]$$$, a valid jump sequence could have distances of $$$3, 9, 3$$$ blocks.
Froggy can also earn points by landing on scoring blocks. For each scoring block he lands on, he will earn $$$1$$$ point. However, he gets points only if he completes the game. In the example above, he completes the game with $$$2$$$ points, which is the maximum achievable score.
Your task is to determine if Froggy can complete the game, and if so, determine the maximum possible score he can achieve.
The first line of the input contains one integer $$$N$$$ $$$(1 \le N \le 2 \times 10^5)$$$, representing the number of jumping platforms.
The second line of the input contains $$$N$$$ integers $$$A_i$$$ $$$(1 \le A_i \lt 10^9, A_i \text{ is odd})$$$, representing the width of each jumping platform.
The third line of the input contains $$$N$$$ integers $$$D_i$$$ $$$(1 \le D_i \le 10^9)$$$, representing the distance between each jumping platform and its previous platform.
The fourth line of the input contains $$$N$$$ integers $$$K_i$$$ $$$(1 \le K_i \le 10^9)$$$, representing the maximum number of blocks Froggy can jump for each jump.
If it is impossible to complete the game, you should print -1.
Otherwise, you should print the maximum achievable score on a single line.
33 5 11 3 24 10 3
2
211 53 35 5
-1
23 31 15 2
0
In Sample 1, the platforms and Froggy's moves are shown in Figures 1 and 2 above.
