Sites de Cracovie#405

Sites de Cracovie

1 seconde
256 mégaoctets
Medium

Sakurako arrive à Cracovie et, comme tout autre touriste, souhaite visiter tous les sites de cette ville. Mais le problème est qu'il y aura bientôt un concours, donc elle doit se dépêcher.

Il y a sites décrits par une paire de nombres (le -ème site est décrit par (x_i,y_i)). La bonne nouvelle est qu'elle a emmené son animal de compagnie Martel, qui peut changer les coordonnées de n'importe quel endroit de à si x^2+y^2=a^2+b^2.

Sakurako commence ses visites depuis son hôtel aux coordonnées et souhaite y retourner. Elle vous demande de trouver le carré de la longueur du chemin minimum qui visite tous les lieux et revient à l'hôtel.

La distance entre les points et est définie comme \sqrt{(a-x)^2+(b-y)^2}.

Input

La première ligne contient un entier (1\le n\le 2\cdot 10^5) — le nombre de points.

La deuxième ligne contient entiers x_1,x_2,\dots,x_n (-10^9\le x_i\le 10^9) — la première coordonnée des sites.

La troisième ligne contient entiers y_1,y_2,\dots,y_n (-10^9\le y_i\le 10^9) — la deuxième coordonnée des sites.

Output

Affichez un entier — le carré de la longueur du chemin minimum après avoir appliqué un nombre quelconque de changements de coordonnées (éventuellement zéro).

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Dans le premier exemple, il peut être prouvé que nous n'avons pas besoin de changer de coordonnées. Ainsi, nous voyageons du point au qui a une distance \sqrt{2 \cdot 2+3 \cdot 3}=\sqrt{4+9}=\sqrt{13} dans les deux directions. Donc la réponse est 2\cdot \sqrt{13} et son carré est .

Dans le deuxième exemple, nous pouvons changer le deuxième point de à puisque 0 \cdot 0+(-4) \cdot (-4)=0 \cdot 0+4 \cdot 4. Ensuite, Sakurako va de à avec une distance de , de à avec une distance de , et de à avec une distance de et la même chose dans l'autre direction. Donc, la réponse est (1+3+5) \cdot 2=18. Et le carré de cela est .

Scoring

  1. ( points): x_i^2+y_i^2\le 18 pour tout ;

  2. ( points): n=1;

  3. ( points): n\le 10;

  4. ( points): sans contraintes supplémentaires.