Krakovun Görməli Yerləri#405

Krakovun Görməli Yerləri

1 saniyə
256 meqabayt
Medium

Sakurako Krakova gəlir və digər turistlər kimi bu şəhərdəki bütün görməli yerləri ziyarət etmək istəyir. Lakin problem ondadır ki, çox tezliklə bir müsabiqə olacaq, buna görə də o tələsməlidir.

Hər biri bir cüt ədəd ilə təsvir olunan ədəd görməli yer var (i-ci görməli yer (x_i,y_i) ilə təsvir olunur). Yaxşı xəbər odur ki, o, Martel adlı ev heyvanını özü ilə götürüb, bu heyvan hər hansı yerin koordinatını -dən -yə dəyişə bilər, əgər x^2+y^2=a^2+b^2 olarsa.

Sakurako ziyarətlərinə koordinatındakı otelindən başlayır və oraya geri dönmək istəyir. O, sizdən bütün yerləri ziyarət edən və otelə geri dönən minimum yolun uzunluğunun kvadratını tapmağı xahiş edir.

və nöqtələri arasındakı məsafə \sqrt{(a-x)^2+(b-y)^2} kimi müəyyən edilir.

Input

Birinci sətirdə bir tam ədəd (1\le n\le 2\cdot 10^5) — nöqtələrin sayı verilir.

İkinci sətirdə sayda tam ədəd x_1,x_2,\dots,x_n (-10^9\le x_i\le 10^9) — görməli yerlərin birinci koordinatı verilir.

Üçüncü sətirdə sayda tam ədəd y_1,y_2,\dots,y_n (-10^9\le y_i\le 10^9) — görməli yerlərin ikinci koordinatı verilir.

Output

Bir tam ədəd çıxarın — koordinatlara istənilən sayda (ola bilsin ki, sıfır) dəyişiklik etdikdən sonra minimum yolun uzunluğunun kvadratı.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Birinci nümunədə, heç bir koordinatı dəyişdirməyə ehtiyac olmadığını sübut etmək olar. Beləliklə, nöqtəsindən nöqtəsinə səyahət edirik, hansı ki, hər iki istiqamətdə məsafəsi \sqrt{2 \cdot 2+3 \cdot 3}=\sqrt{4+9}=\sqrt{13}-dür. Beləliklə, minimum yolun uzunluğu 2\cdot \sqrt{13}-dür və onun kvadratı -dir.

İkinci nümunədə, ikinci nöqtəni -dən -ə dəyişə bilərik, çünki 0 \cdot 0+(-4) \cdot (-4)=0 \cdot 0+4 \cdot 4. Sonra, Sakurako -dan -ə məsafəsi olan, -dən -ə məsafəsi olan, və -dən -a məsafəsi olan və əks istiqamətdə də eyni yollar ilə gedir. Beləliklə, minimum yolun uzunluğu (1+3+5) \cdot 2=18-dir. Və onun kvadratı -dür.

Scoring

  1. ( bal): x_i^2+y_i^2\le 18 bütün -lər üçün;

  2. ( bal): n=1;

  3. ( bal): n\le 10;

  4. ( bal): əlavə məhdudiyyətlər olmadan.