Maximum Weight Subset of Vectors

Given a set of n two-dimensional vectors \((x, y)\), the weight of a vector is defined as \(x^2 + y^2\). The task is to choose a subset of these vectors such that the weight of their sum is maximized. Let the sum of the chosen vectors be \(S = (S_x, S_y)\); you need to maximize \(S_x^2 + S_y^2\).

Note: You may assume that \(1 \leq n \leq 20\). The input also guarantees that all values are integers.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 20\)), representing the number of vectors. Each of the following \(n\) lines contains two space-separated integers \(x\) and \(y\), denoting the coordinates of a vector.

outputFormat

Output a single integer which is the maximum weight, i.e., the value of \(S_x^2 + S_y^2\) for an optimal subset of the given vectors.

sample

3
1 2
-2 3
3 -4

34