import qualified Data.Set as S

inf = 10^32 :: Integer

main = do
 n <- readLn
 xys <- map (map read . words) . lines <$> getContents :: IO [[Integer]]
 print (mama n xys)

mama :: Int -> [[Integer]] -> Integer
mama n xys = S.foldr (minDiff s2) inf s1
 where
  (xys1,xys2) = splitAt (div n 2) xys
  s1 = foldr dp (S.singleton 0) xys1
  s2 = foldr dp (S.singleton 0) xys2

minDiff :: S.Set Integer -> Integer -> Integer -> Integer
minDiff s2 x d = min d (min du dl)
 where
  du = maybe inf (abs.(x+)) (S.lookupGE (-x) s2)
  dl = maybe inf (abs.(x+)) (S.lookupLE (-x) s2)

dp :: [Integer] -> S.Set Integer -> S.Set Integer
dp [x,y] = S.fromList . concatMap (\e -> [e+x,e-y]) . S.toList