【CodeForces - 1047B 】Cover Points （数学，构造，思维）

题干：

There are nn points on the plane, (x1,y1),(x2,y2),…,(xn,yn)(x1,y1),(x2,y2),…,(xn,yn).

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

Input

First line contains one integer nn (1≤n≤1051≤n≤105).

Each of the next nn lines contains two integers xixi and yiyi (1≤xi,yi≤1091≤xi,yi≤109).

Output

Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.

Examples

Input

3 1 1 1 2 2 1

Output

3

Input

4 1 1 1 2 2 1 2 2

Output

4

Note

Illustration for the first example: 

Illustration for the second example: 

解题报告：

    这题比较巧妙的一个地方在于，要求次短边的最小长度，其实也就是最长直角边的最短长度（因为斜边肯定最长）。所以既然要最短，那么等腰直角三角形，所以，，看代码就理解了。

AC代码：

#include<bits/stdc++.h> #define ll long long using namespace std;int main() {int n;cin>>n;ll ans = -1;int a,b;for(int i = 1; i<=n; i++) {scanf("%d%d",&a,&b);ans = max(ans,(ll)a+b);}cout << ans << endl;return 0; }

 

总结

以上是生活随笔为你收集整理的【CodeForces - 1047B 】Cover Points （数学，构造，思维）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。