Maximum Vector Sum

A two-dimensional vector can be represented by two integer coordinates (X, Y).

When two or more vectors are added, their corresponding coordinates are added separately. For instance, (1, 2) + (3, 4) + (5, 6) = (1 + 3 + 5, 2 + 4 + 6) = (9, 12).

The weight of a vector (x, y) is defined as x * x + y * y.

You are given N nonzero vectors in the plane. Write a program that chooses some of these vectors so that the weight of the sum of all chosen vectors is as large as possible.

Intermediate calculations and the answer may require 64-bit integers.

The first line contains the number of vectors N, where 1 <= N <= 30,000.

Each of the next N lines contains two coordinates X and Y, separated by one space.

Each coordinate satisfies -30,000 <= X, Y <= 30,000, and no given vector is (0, 0).

Print one line containing the maximum possible weight of the sum of the chosen vectors.