Năm 20XX, IOI sẽ được tổ chức tại đất nước nơi JOI sinh sống. Nghe tin này, JOI vội lao ra khỏi phòng để báo cho bạn bè. Vì quá hấp tấp, cậu va vào giá sách khiến toàn bộ sách rơi xuống. Đang rất vội, cậu nhặt tất cả sách đặt lại lên giá mà không quan tâm đến thứ tự rồi ra khỏi nhà. Khi trở về, JOI phải sắp xếp những cuốn sách đang lộn xộn về thứ tự ban đầu.

Giá sách trong phòng JOI rộng \(N\) xentimét, chứa \(N\) cuốn sách, mỗi cuốn rộng \(1\) xentimét. Các cuốn sách được đánh số từ \(1\) đến \(N\) và ban đầu được xếp từ trái sang phải theo thứ tự \(1,\ldots,N\). Cuốn sách \(i\) nặng \(A_i\) gam.

JOI đang mệt và không muốn cầm nhiều sách cùng lúc, nên cậu quyết định sắp xếp giá sách bằng cách lặp lại thao tác sau:

1. Chọn một cuốn sách trên giá và lấy nó ra.
2. Dịch chuyển các cuốn sách nằm cạnh chỗ trống vừa tạo ra vào chỗ trống; có thể thực hiện việc này nhiều lần.
3. Đặt cuốn sách đã lấy ra vào chỗ trống trên giá.

Không được lấy từ hai cuốn sách trở lên ra khỏi giá cùng một lúc.

Ví dụ, nếu sách đang được xếp từ trái sang phải theo thứ tự \(5,3,4,1,2\), JOI có thể lấy cuốn \(1\) ra, lần lượt dịch cuốn \(4\) rồi cuốn \(3\) sang phải và đặt cuốn \(1\) lại lên giá. Khi đó thứ tự sách từ trái sang phải trở thành \(5,1,3,4,2\), như hình dưới.

Khi lấy một cuốn sách nặng \(w\) gam ra khỏi giá, JOI tiêu hao đúng \(w\) calo. Khi đặt cuốn sách nặng \(w\) gam trở lại giá, cậu cũng tiêu hao đúng \(w\) calo. Giá sách được làm bằng vật liệu nhẵn, nên có thể coi việc dịch chuyển sách trong giá không tiêu hao calo.

Vì đang mệt, JOI muốn đưa sách về thứ tự ban đầu với lượng calo tiêu hao ít nhất.

Yêu cầu

Cho số cuốn sách, khối lượng của từng cuốn và thứ tự hiện tại trên giá, hãy tính tổng số calo ít nhất mà JOI cần tiêu hao để đưa sách về thứ tự ban đầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo mô tả khối lượng sách. Dòng thứ \(i+1\) \((1\le i\le N)\) chứa số nguyên \(A_i\), là khối lượng tính bằng gam của cuốn sách \(i\).
• \(N\) dòng tiếp theo mô tả thứ tự sách hiện tại. Dòng thứ \(j+N+1\) \((1\le j\le N)\) chứa số hiệu của cuốn sách đang ở vị trí thứ \(j\) từ trái sang.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số nguyên là tổng số calo ít nhất mà JOI phải tiêu hao.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le A_i\le1\,000\,000\,000\) với mọi \(1\le i\le N\).
• Thứ tự hiện tại chứa mỗi cuốn sách từ \(1\) đến \(N\) đúng một lần.

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(1\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỷ lệ dưới đây mô tả các tập dữ liệu có phần giao nhau:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le5\,000\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(A_i=1\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn đồng thời \(N\le5\,000\) và \(A_i=1\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: \(N\le5\,000\); hoặc \(A_i=1\) với mọi \(1\le i\le N\).

Ví dụ

4
1
6
4
3
3
4
2
1

14