题目描述

给定 $n$ 个二维向量，其中第 $i$ 个向量记作 $(x_i, y_i)$。每个向量对应一种移动操作，其中第 $i$ 个向量表示将点 $(s, t)$ 移动到 $(s+x_i, t+y_i)$ 。

请从中挑选任意数量的向量，使得从原点出发的点，经过向量的移动之后，终点的 x 坐标的绝对值与 y 坐标的绝对值之和达到最大。

输入格式

• 单个整数：表示 $n$
• 第二行到第 $n+1$ 行：每行两个整数 $x_i$ 与 $y_i$。

输出格式

• 单个整数：表示终点的x坐标绝对值与y坐标绝对值之和的最大值。

4
-100 99
1 100
-1 -100
100 -99

298

样例解释 1

(-1 -100) (100 -99)

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$
• 对于 $60\%$ 的数据，$1\leq n\leq 500$
• 对于 $100\%$ 的数据，$1\leq n\leq 300,000$
• $-10^9\leq x_{i}, y_i\leq 10^9$