Shobon đã quyết định sử dụng AI tạo sinh để hỗ trợ phát triển một dự án phần mềm. Dự án bao gồm $N$ công việc. Mỗi công việc $i$ ($i = 1, 2, \dots, N$) có khối lượng cài đặt được xác định trước là $A_i$ và độ phức tạp là $B_i$.

Shobon có thể thực hiện các công việc này theo bất kỳ thứ tự nào. Tuy nhiên, anh ấy không thể làm nhiều hơn một công việc cùng một lúc.

Mỗi công việc $i$ ($i = 1, 2, \dots, N$) có thể được hoàn thành theo một trong hai cách sau:

• Tự cài đặt thủ công. Shobon tự viết mã, tốn $A_i$ đơn vị thời gian.
• Sử dụng AI tạo sinh. Để AI sinh ra mã đúng, Shobon giải thích công việc hiện tại và tất cả các công việc đã hoàn thành trước đó cho AI. Gọi $S$ là tổng độ phức tạp của tất cả các công việc đã hoàn thành trước đó. Việc chuẩn bị lời giải thích này tốn $S + B_i$ đơn vị thời gian. Sau đó AI hoàn thành việc cài đặt ngay lập tức, nên không cần thêm thời gian cài đặt. Do đó, hoàn thành công việc này bằng cách sử dụng AI tốn tổng cộng $S + B_i$ đơn vị thời gian.

Bất kể phương pháp nào được sử dụng, một khi công việc $i$ đã hoàn thành, độ phức tạp $B_i$ của nó sẽ được tính vào các giá trị tương lai của $S$ khi sử dụng AI tạo sinh.

Hãy tìm tổng thời gian tối thiểu cần thiết để hoàn thành tất cả các công việc.

Dữ liệu vào

Dữ liệu vào gồm ba dòng theo định dạng sau:

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \end{aligned} $$

Ở dòng đầu tiên, số lượng công việc $N$ được cho ($1 \le N \le 2 \times 10^5$). Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$, mỗi số nằm trong khoảng từ $1$ đến $10^9$ (bao gồm cả hai đầu mút), biểu thị khối lượng cài đặt của $N$ công việc. Dòng thứ ba chứa $N$ số nguyên $B_1, B_2, \dots, B_N$, mỗi số nằm trong khoảng từ $1$ đến $10^8$ (bao gồm cả hai đầu mút), biểu thị độ phức tạp của $N$ công việc.

Dữ liệu ra

In ra trên một dòng tổng thời gian tối thiểu cần thiết để hoàn thành tất cả các công việc.

Ví dụ

Dữ liệu vào 1

3
10 6 10
5 2 4

Dữ liệu ra 1

18

Dữ liệu vào 2

1
4
10

Dữ liệu ra 2

4

Dữ liệu vào 3

5
100 100 100 100 100
5 1 4 2 3

Dữ liệu ra 3

35

Dữ liệu vào 4

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

Dữ liệu ra 4

118

Ghi chú

Đối với Ví dụ 1, xét việc sử dụng AI tạo sinh cho công việc $2$ và $3$ theo thứ tự này, sau đó tự cài đặt thủ công công việc $1$.

• Khi bắt đầu công việc $2$, chưa có công việc nào được hoàn thành. Công việc này tốn $0 + B_2 = 2$ đơn vị thời gian.
• Khi bắt đầu công việc $3$, công việc $2$ đã được hoàn thành. Công việc này tốn $B_2 + B_3 = 2 + 4 = 6$ đơn vị thời gian.
• Cuối cùng, tự cài đặt thủ công công việc $1$ tốn $A_1 = 10$ đơn vị thời gian.

Như vậy, tất cả các công việc có thể được hoàn thành trong $2 + 6 + 10 = 18$ đơn vị thời gian, đây là giá trị nhỏ nhất có thể.