Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |

## MVECTOR - Sum of Vectors |

English | Vietnamese |

We can represent a 2D vector as a pair (X, Y). The sum of two or more vectors is a vector whose coordinates are the sums of the corresponding coordinates of all the vectors in the sum. e.g. (1, 2) + (3, 4) + (5, 6) = (1 + 3 + 5, 2 + 4 + 6) = (9, 12) Weight of a vector (x, y) is defined as x * x + y * y. You are given N vectors on a plain.

Your task is to write a program that will determine a subset of those vectors so the weight of the sum of all vectors in that subset is maximal.

Note: Use 64-bit integers (int64 in pascal or long long in c)

### Input

In the first line of the input file is an integer N, 1 ≤ N ≤ 30,000, the number of vectors.

The following N lines contain descriptions for each of the vectors. A description is made of two integers X and Y, separated by a single blank, -30,000 ≤ X, Y ≤ 30,000.

None of the given vectors will be (0, 0)

### Output

In the first and only line of the output file you have to write the weight of the maximum sum.

### Sample

Input:5 5 -8 -4 2 4 -2 2 1 -6 4Output:202

Input:4 1 4 -1 -1 1 -1 -1 4Output:64

Input:9 0 1 6 8 0 -1 0 6 -1 1 -1 2 5 -4 1 0 6 -5Output:360

Được gửi lên bởi: | psetter |

Ngày: | 2009-03-22 |

Thời gian chạy: | 1s |

Giới hạn mã nguồn: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |

Nguồn bài: | COI 03 |