Một bức tường gồm \(n\) cột đứng kề nhau, cột \(i\) cao \(a_i\) và rộng \(1\). Cột \(i\) được chia thành \(b_i\) phần có chiều cao bằng nhau. Dùng một nét bút có thể vẽ một đoạn thẳng mà không nhấc bút. Hãy vẽ toàn bộ biên các cột và các đường phân chia bằng số đoạn thẳng ít nhất.

Dữ liệu vào

Dòng đầu chứa \(n\) (\(1\le n\le10^5\)). Dòng hai chứa \(a_1,\ldots,a_n\) (\(1\le a_i\le10^9\)). Dòng ba chứa \(b_1,\ldots,b_n\) (\(1\le b_i\le10^9\)).

Dữ liệu ra

In số đoạn thẳng nhỏ nhất cần vẽ.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(11\) điểm: \(N=1\).
2. \(13\) điểm: \(N=2\), \(1\le a_i,b_i\le10\).
3. \(29\) điểm: \(a_i\le10^6\) và \(b_i\) chia hết \(a_i\) với mọi \(i\).
4. \(57\) điểm: không có ràng buộc thêm.

Ví dụ

3
4 6 4
2 3 4

10

3
4 6 3
3 3 2

12

Nguồn

COCI 2025/2026 - Vòng 3, bài Ravnalo.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.