Description

Zvonkec has to refactor one source code file every day. What frustrates him is that the code style is strange. He is especially bothered by uneven indentation, that is, the number of tab characters (the Tab key on the keyboard) at the beginning of each line.

Fortunately, his editor has commands that can select a consecutive group of lines and add or delete characters at the beginning of each line. Please help Zvonkec tidy up the code as quickly as possible.

You are given the number of lines $n$, a sequence specifying the current number of tab characters at the beginning of each line, and a sequence specifying the desired number of tab characters at the beginning of each line.

Zvonkec can execute many commands, each command consists of:

• Selecting any number of consecutive lines.
• Adding or deleting exactly one tab character at the beginning of every selected line.

No matter how many lines are selected, the two actions above together count as one command.

Note that it is forbidden to delete more tab characters from a line than the line actually has at its beginning, because the editor would then start deleting characters other than tabs.

You need to compute the minimum number of commands required to tidy up the code.

Input Format

The input consists of three lines.

The first line contains a positive integer $n$.

The second line contains $n$ integers $p_i$, where $p_i$ is the number of tab characters at the beginning of line $i$ before any editing.

The third line contains $n$ integers $k_i$, where $k_i$ is the number of tab characters Zvonkec wants at the beginning of line $i$.

Output Format

Output one line.

The line contains one positive integer, the minimum number of commands required.

3
3 4 5
6 7 8 

3

4
1 2 3 4
3 1 1 0 

6

4
5 4 5 5
1 5 0 1 

10

Hint

Constraints

• For $70\%$ of the testdata, $1 \leq n \leq 100$, $0 \le p_i \le 80$, $0 \leq k_i \leq 80$.
• For $100\%$ of the testdata, $1 \leq n \le 1000$, $0 \le p_i \le 80$, $0 \leq k_i \leq 80$.

Notes

Translated from COCI2010-2011 CONTEST #1 T5 TABOVI.

Translated by ChatGPT 5