Maximum Euclidean Distance of Chess Piece Moves

A chess piece is placed at the origin \((0,0)\) of an infinite two-dimensional plane. You are given \(n\) move instructions, each represented by a two-dimensional integer vector \((x, y)\). Each move instruction can be executed at most once (or skipped). The chess piece may pass through the same point multiple times, and different instructions may have identical direction vectors.

Your goal is to choose a subset of these instructions to execute so that the resulting position of the chess piece is as far away from the origin as possible in terms of Euclidean distance.

More formally, if you choose a subset \(S\) of the instructions with vectors \(\{(x_i,y_i)\}_{i\in S}\), then the final position will be \((X,Y)=\Big(\sum_{i\in S}x_i,\;\sum_{i\in S}y_i\Big)\) and its Euclidean distance is given by:

[ D=\sqrt{X^2+Y^2}. ]

Determine the maximum possible distance \(D\) that can be achieved.

inputFormat

The input begins with a line containing a single integer \(n\) (\(1 \le n \le 20\)), representing the number of move instructions. Each of the following \(n\) lines contains two space-separated integers \(x\) and \(y\) (\(-10^4 \le x,y \le 10^4\)), representing a move instruction.

outputFormat

Output the maximum Euclidean distance achievable from the origin. The answer is considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3
1 2
3 4
-1 -1

7.211103