\(N\) con bò của Farmer John rất khắt khe về nhiệt độ trong chuồng. Một số con thích nhiệt độ mát hơn, trong khi những con khác thích ấm hơn.

Chuồng của Farmer John có một dãy \(N\) ô chuồng, được đánh số \(1 \ldots N\), mỗi ô chứa đúng một con bò. Con bò thứ \(i\) muốn nhiệt độ ô của mình là \(p_i\), còn nhiệt độ hiện tại trong ô là \(t_i\). Để đảm bảo mọi con bò đều thoải mái, Farmer John lắp đặt một hệ thống điều hòa mới được điều khiển theo cách khá thú vị. Ông có thể gửi lệnh cho hệ thống để tăng hoặc giảm nhiệt độ của một dãy ô chuồng liên tiếp đúng \(1\) đơn vị — ví dụ: "tăng nhiệt độ trong các ô \(5 \ldots 8\) thêm 1 đơn vị". Dãy ô chuồng có thể chỉ gồm một ô.

Hãy giúp Farmer John xác định số lệnh ít nhất cần gửi cho hệ thống điều hòa mới để nhiệt độ trong mỗi ô chuồng đạt mức lý tưởng của con bò sống tại đó.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên không âm \(p_1 \ldots p_N\), cách nhau bởi dấu cách. Dòng cuối cùng chứa \(N\) số nguyên không âm \(t_1 \ldots t_N\).

Dữ liệu ra

In ra một số nguyên duy nhất là số lệnh ít nhất Farmer John cần sử dụng.

Phân nhóm

• Dữ liệu 2–5: \(N \leq 100\).
• Dữ liệu 6–8: \(N \leq 1000\).
• Dữ liệu 9–10: \(N \leq 100\,000\).
• Trong dữ liệu 1–6 và 9, các giá trị nhiệt độ không vượt quá \(100\).
• Trong dữ liệu 7–8 và 10, các giá trị nhiệt độ không vượt quá \(10\,000\).

Ví dụ

5
1 5 3 3 4
1 2 2 2 1

5

Nhiệt độ ban đầu: 1 2 2 2 1
Tăng các ô 2..5: 1 3 3 3 2
Tăng các ô 2..5: 1 4 4 4 3
Tăng các ô 2..5: 1 5 5 5 4
Giảm các ô 3..4: 1 5 4 4 4
Giảm các ô 3..4: 1 5 3 3 4

Nguồn

USACO 2021 December Contest, Bronze — Air Cownditioning. Tác giả: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=1156