Cho \(n\) vectơ trên hệ trục tọa độ Descartes, vectơ thứ \(i\) \((1 \leq i \leq n)\) có tọa độ \((x_{i}, y_{i})\). Hãy chọn một tập hợp các vectơ đã cho sao cho độ dài của tổng các vectơ là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 2 \times 10^{5})\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((|x_{i}|, |y_{i}| \leq 10^{4})\).

Output

• Một dòng duy nhất chứa một số nguyên là bình phương độ dài lớn nhắt.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 2 \times 10^{3}\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5
2 -2
-2 -2
0 2
3 1
-3 1

Output

26

Note

Một phương án tối ưu là là chọn tập gồm các vectơ \((0, 2)\), \((3, 1)\) và \((2, -2)\).