Cuối cùng, Ami cũng trúng giải xổ số độc đắc và mời được Cuom1999 về dạy toán cho mình. Thấy Ami yếu phần trị tuyệt đối và bất phương trình, Cuom1999 quyết định dạy cho Ami những bài toán tìm Min. Cuom1999 cho Ami 2 dãy số a và b gồm n phần tử được đánh số từ 1 đến n. Cuom1999 muốn Ami chọn ra một số x sao cho biểu thức sau đạt giá trị nhỏ nhất

          S = |a₁ – x * gcd(a₁ , b₁)| + |a₂ – x * gcd(a₂ , b₂)| + …. + |a_n – x * gcd(a_n,b_n)|.

Các kí hiệu |x| là giá trị tuyệt đối của x và gcd(x,y) là ước chung lớn nhất của x và y. Các bạn hãy giúp Ami chọn ra một số x sao cho S đạt giá trị bé nhất nhé.

Dữ liệu vào

Dòng đầu là 1 số nguyên dương n (n <= 2 * 10⁵) là số phần tử của 2 dãy.

Dòng tiếp theo là n số nguyên dương a₁,a₂,…,a_n (a_i <= 10⁹) là các phần tử của dãy a.

Dòng tiếp theo là n số nguyên dương b₁,b₂,…,b_n (b_i <= 10⁹) là các phần tử của dãy b.

Dữ liệu ra

Một số nguyên là tổng S nhỏ nhất có thể đạt được.