시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB152267653752.493%

문제

N(1 ≤ N ≤ 50,000)개의 점들이 있을 때, 최대 L1-metric 거리를 찾으시오.

두 점의 좌표가 (a, b), (c, d)일 때, 두 점의 L1-metric 거리는 |a-c|+|b-d|이다.

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다.

출력

첫째 줄에 최대 거리를 출력한다.

예제 입력 1

5
1 1
3 5
2 7
8 1
4 4

예제 출력 1

12
W3sicHJvYmxlbV9pZCI6IjIzODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDAgXHVhYzcwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5OKDEgJmxlOyBOICZsZTsgNTAsMDAwKVx1YWMxY1x1Yzc1OCBcdWM4MTBcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwIEwxLW1ldHJpYyBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjYzNlXHVjNzNjXHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCAoYSwgYiksIChjLCBkKVx1Yzc3YyBcdWI1NGMsIFx1YjQ1MCBcdWM4MTBcdWM3NTggTDEtbWV0cmljIFx1YWM3MFx1YjlhY1x1YjI5NCB8YS1jfCt8Yi1kfFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxtZXRhIGNoYXJzZXQ9XCJ1dGYtOFwiPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVjNzU4IHgsIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODhjXHVkNDVjXHVjNzU4IFx1YmM5NFx1YzcwNFx1YjI5NCAtMSwwMDAsMDAwXHVjNzc0XHVjMGMxIDEsMDAwLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYXZlIENvd3MgMyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4mIzM5O3MgTiAoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCkgY293cyBhcmUgZXhwbG9yaW5nIGEgbGFyZ2Ugcm9vbSBpbiBhIGNhdmUuICZuYnNwO0l0IGlzIGRhcmssIGFuZCB0aGUgY293cyBjb21tdW5pY2F0ZSBieSBtb29pbmcgbG91ZGx5IGF0IGVhY2ggb3RoZXIuICZuYnNwO0R1ZSB0byB0aGUgc3RyYW5nZSBhY2NvdXN0aWNzIG9mIHRoZSByb29tLCB0aGUgdGltZSBpdCB0YWtlcyBmb3IgYSAmIzM5O21vbyYjMzk7IGZyb20gb25lIGNvdyB0byByZWFjaCBhbm90aGVyIGNvdyBpcyBwcm9wb3J0aW9uYWwgdG8gdGhlICZxdW90O21hbmhhdHRhbiZxdW90OyBkaXN0YW5jZSBiZXR3ZWVuIHRoZSB0d28gY293czogdGhhdCBpcywgaWYgY293IEEgaXMgYXQgbG9jYXRpb24gKFhhLCBZYSkgYW5kIGNvdyBCIGlzIGF0IGxvY2F0aW9uIChYYiwgWWIpLCBpdCB0YWtlcyB8WGEtWGJ8ICsgfFlhLVlifCB1bml0cyBvZiB0aW1lIGZvciBhICYjMzk7bW9vJiMzOTsgZnJvbSBjb3cgQSB0byByZWFjaCBjb3cgQi4gWCBhbmQgWSBjb29yZGluYXRlcyBhcmUgYWxsIGluIHRoZSByYW5nZSAoLTEsMDAwLDAwMCAuLiAxLDAwMCwwMDApLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbG9jYXRpb25zIG9mIHRoZSBOIGNvd3MsIGRldGVybWluZSB0aGUgbWF4aW11bSB0aW1lIG92ZXIgYWxsIHBhaXJzIG9mIGNvd3MgZm9yIGEgJiMzOTttb28mIzM5OyB0byBwcm9wYWdhdGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlcjogTjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBnaXZpbmcgdGhlICh4LHkpIGNvb3JkaW5hdGVzIG9mIGEgY293PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1heGltdW0gJiMzOTttb28mIzM5OyBkaXN0YW5jZSBhbW9uZyBhbGwgcGFpcnMgb2YgY293czxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IjxwPlRoZSBjb3dzIGF0ICgyLDcpIGFuZCAoOCwxKSBhcmUgc2VwYXJhdGVkIGJ5IHwyLTh8ICsgfDctMXwgPSA2ICsgNiA9IDEyIHVuaXRzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==