Writing

Takis's Ovens

Another day of hard work has come to an end, and it is time for the pizzeria to close. However, there is a problem! Today, Takis's assistant took the day off, and Takis does not know how to turn off his ovens by himself.

Specifically, the pizzeria has ~N~ ovens, numbered from ~1~ to ~N~, and correspondingly ~N~ switches. Some of the ovens are initially on, while the others are initially off. We denote the initial state of the ~i~-th oven by ~a_i~: ~a_i = 1~ if it is on and ~a_i = 0~ if it is off.

The pizzeria's switches work in a special way: using the ~i~-th switch flips the state of the ~i~-th oven and the next ~k_i~ ovens (where ~k_i~ is the "characteristic number" of the ~i~-th switch); that is, the ovens among them that are on are turned off, and those that are off are turned on.

Takis must turn off all the ovens, but since he is in a hurry, he wants to do so as quickly as possible. What is the minimum number of switches he needs to use to achieve this?

Problem

Write a C++ program that reads the input data from oven.in and writes the results to oven.out.

Input Files (ovens.in)

The first line contains an integer ~N~: the number of ovens and switches in the pizzeria.

The second line contains ~N~ integers ~a_1~, ~a_2~, ~...~, ~a_N~: the initial states of the ovens, where ~1~ represents an oven that is on and ~0~ represents an oven that is off.

The third line contains ~N~ integers ~k_1~, ~k_2~, ~...~, ~k_N~: the characteristic numbers of the switches.

Output Files (ovens.out)

The output must contain a single line with an integer: the minimum number of switches Takis needs to use to turn off all the ovens.

Sample Input and Output Files

Input:

6
1 0 0 1 1 0
3 2 3 1 1 0

Output:

3

Explanation:

Takis can turn off all the ovens using ~3~ switches, as follows:

1. He uses the ~4~-th switch, which flips the state of the ~4~-th oven and the next oven. The state of the ovens becomes ~[1,\;0,\;0,\;0,\;0,\;0]~.

2. He uses the ~2~-nd switch, which flips the state of the ~2~-nd oven and the next two ovens. The state of the ovens becomes ~[1,\;1,\;1,\;1,\;0,\;0]~.

3. He uses the ~1~-st switch, which flips the state of the ~1~-st oven and the next three ovens. The state of the ovens becomes ~[0,\;0,\;0,\;0,\;0,\;0]~.

Furthermore, it can be proven that Takis cannot turn off all the ovens using fewer than ~3~ switches. Therefore, the answer is ~3~.

Constraints

• ~1 \le N \le 200.000~
• ~0 \le a_i \le 1~
• ~0 \le k_i \le N - i~

Subtasks

1. (11 points) ~k_i = 0~ for every ~i~ (where \(1 \\le i \le N\)).
2. (17 points) ~a_i = 1~ for every ~i~ (where \(1 \\le i \le N\)).
3. (21 points) ~k_i \le 10~ for every ~i~ (where \(1 \\le i \le N\)).
4. (24 points) ~k_i = N - 1~ for every ~i~ (where ~1 \le i \le N~).
5. (27 points) There are no further restrictions.

Notes

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~1~ sec.
• Maximum available memory: ~64~ MB.

Warning: The answer may exceed ~2^{32}~ and, in general, you may need to perform operations with numbers larger than those that can be represented by the basic int type. Also, make sure to read the input and print the output efficiently in problems that require it.