Những ngày đầu năm 1975, khắp miền quê rộn ràng không khí chờ đợi chiến thắng. Ở một vùng đồng bằng rộng lớn, có $n$ ngôi làng nằm dọc theo một con đường duy nhất — trục số. Người dân nơi đây mong mỏi từng giờ được nghe bản tin chiến thắng vang lên từ trạm phát sóng mới mà chính quyền đang gấp rút xây dựng.

Mỗi ngôi làng $i$ nằm ở vị trí ~x_i~ trên trục số, và người dân ở đó có mức mong ngóng tin chiến thắng ~w_i~.

Tín hiệu từ trạm đặt ở vị trí $p$ suy giảm theo khoảng cách, tức mỗi làng $i$ cảm nhận tín hiệu với mức suy giảm là: ~ f_i = |x_i - p| \cdot w_i~

Yêu cầu: Hãy giúp chọn vị trí nguyên $p$ $(1 \leq p \leq 10^9)$ đặt trạm phát sóng sao cho ~\max_{i=1}^{n} f_i~là nhỏ nhất có thể.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên ~n~ ~(1 \le n \le 2 \times 10^5)~ — số ngôi làng.
• Dòng thứ hai gồm ~n~ số nguyên ~x_1, x_2, \dots, x_n~ ~(1 \le x_i \le 2 \times 10^5)~ — vị trí của từng làng.
• Dòng thứ ba gồm ~n~ số nguyên ~w_1, w_2, \dots, w_n~ ~(1 \le w_i \le 2 \times 10^6)~ — mức mong ngóng của từng làng.

Kết quả

• Một số nguyên — mức mất mát tín hiệu lớn nhất là nhỏ nhất có thể.

Ràng buộc

• Subtask $1$ ($30\%$): $n \leq 1000$
• Subtask $2$ ($70\%$): Không có giới hạn gì thêm

Ví dụ

Dữ liệu vào

3
1 5 9
1 2 1

Kết quả ra

4