Սակուրակոն հասնում է Կրակով և, ինչպես ցանկացած այլ զբոսաշրջիկ, ցանկանում է այցելել այս քաղաքի բոլոր տեսարժան վայրերը: Բայց խնդիրը այն է, որ շատ շուտով մրցույթ է լինելու, այնպես որ նա պետք է շտապի:
Կա տեսարժան վայր, որոնք նկարագրված են թվերի զույգով (i-րդ տեսարժան վայրը նկարագրված է (x_i,y_i)): Լավ նորությունն այն է, որ նա վերցրել է իր սիրելի Մարտելին, ով կարող է փոխել ցանկացած վայրի կոորդինատը -ից , եթե x^2+y^2=a^2+b^2:
Սակուրակոն իր այցելությունները սկսում է իր հյուրանոցից, որը գտնվում է կոորդինատում և ցանկանում է վերադառնալ այնտեղ: Նա խնդրում է ձեզ գտնել այն ճանապարհի երկարության քառակուսին, որը այցելում է բոլոր վայրերը և վերադառնում հյուրանոց:
և կետերի միջև հեռավորությունը սահմանվում է որպես \sqrt{(a-x)^2+(b-y)^2}:
Առաջին տողում կա մեկ ամբողջ թիվ (1\le n\le 2\cdot 10^5) — կետերի քանակը:
Երկրորդ տողում կա ամբողջ թիվ x_1,x_2,\dots,x_n (-10^9\le x_i\le 10^9) — տեսարժան վայրերի առաջին կոորդինատը:
Երրորդ տողում կա ամբողջ թիվ y_1,y_2,\dots,y_n (-10^9\le y_i\le 10^9) — տեսարժան վայրերի երկրորդ կոորդինատը:
Արտադրեք մեկ ամբողջ թիվ — նվազագույն ճանապարհի երկարության քառակուսին, կիրառելով ցանկացած քանակությամբ կոորդինատների փոփոխություններ (հնարավոր է զրո):
Example 1
Example 2
Առաջին օրինակին կարելի է ապացուցել, որ մենք չենք պետք փոխել որևէ կոորդինատ: Այսպիսով, մենք ճանապարհորդում ենք կետից , որի հեռավորությունը \sqrt{2 \cdot 2+3 \cdot 3}=\sqrt{4+9}=\sqrt{13} է երկու ուղղություններով: Այսպիսով, պատասխանն է 2\cdot \sqrt{13}, և դրա քառակուսին է:
Երկրորդ օրինակին, մենք կարող ենք փոխել երկրորդ կետը -ից , քանի որ 0 \cdot 0+(-4) \cdot (-4)=0 \cdot 0+4 \cdot 4: Այնուհետև, Սակուրակոն գնում է -ից հեռավորությամբ , -ից հեռավորությամբ , և -ից հեռավորությամբ և նույնը հակառակ ուղղությամբ: Այսպիսով, պատասխանն է (1+3+5) \cdot 2=18: Եվ դրա քառակուսին է:
( միավոր): x_i^2+y_i^2\le 18 բոլոր -երի համար;
( միավոր): n=1;
( միավոր): n\le 10;
( միավոր): առանց լրացուցիչ սահմանափակումների.