Air Cownditioning

Problem Source

USACO December 2021 Bronze Division.

Problem Description

Farmer John's $N$ cows are very picky about the temperature in their barn. Some cows like it cooler, while others prefer it warmer.

Farmer John's barn consists of a row of $N$ stalls, numbered $1 \dots N$, each containing one cow. The $i$-th cow wants her stall's temperature to be $p_i$, but currently her stall's temperature is $t_i$. To keep every cow comfortable, Farmer John installs a new air conditioning system. The system is controlled in an interesting way: he can send commands telling it to raise or lower the temperature of a contiguous range of stalls by $1$ unit — for example, "raise the temperature of stalls $5 \dots 8$ by $1$ unit". The shortest such range can consist of a single stall.

Help Farmer John determine the minimum number of commands he needs to send to the new air conditioning system so that every cow's stall reaches that cow's desired temperature.

Input Format

The first line contains $N$. The next line contains $N$ non-negative integers $p_1, p_2, \dots, p_N$, separated by spaces. The last line contains $N$ non-negative integers $t_1, t_2, \dots, t_N$.

Output Format

Output a single integer — the minimum number of commands Farmer John needs to use.

Sample Input

5
1 5 3 3 4
1 2 2 2 1

Sample Output

5

One optimal set of commands Farmer John can use is:

initial temp     : 1 2 2 2 1
raise stalls 2..5: 1 3 3 3 2
raise stalls 2..5: 1 4 4 4 3
raise stalls 2..5: 1 5 5 5 4
lower stalls 3..4: 1 5 4 4 4
lower stalls 3..4: 1 5 3 3 4

Constraints

• Test cases 2–5 satisfy $N \le 100$.
• Test cases 6–8 satisfy $N \le 1000$.
• Test cases 9–10 satisfy $N \le 100000$.
• In test cases 1–6 and 9, temperature values do not exceed $100$.
• In test cases 7–8 and 10, temperature values do not exceed $10000$.

Problem contributed by Brian Dean.