사격

시간 제한4초메모리 제한1024 MB

요약

각 사격은 그 축에 더 가까운 표적이 남아 있지 않을 때만 가능하다는 조건에서, 좌표축에서 쏴 얻을 수 있는 점수의 최댓값을 구한다.

문제

사격 선수 BOJ 군은 한 사격 대회에 출전한다. 대회는 좌표 평면 위 총 $N$ 개의 표적을 두고 진행된다.

출전한 선수는 총 $N$ 발의 사격을 할 수 있다. 각 사격은 X축 또는 Y축 위에서 이루어져야 하며, 축에 평행한 방향으로만 발사할 수 있다. 한 번 총에 맞은 표적은 파괴되며 선수는 사격 지점과 표적 사이의 거리만큼 점수를 얻는다.

자신감이 없는 BOJ군은 자신이 겨냥하는 표적보다 서 있는 축에 더 가까운 다른 표적이 남아 있다면 사격을 하지 않으려고 한다. 예를 들어, X축에서 (3, 4)의 표적에 사격을 하려면 y좌표가 4 미만인 다른 표적이 있어서는 안 된다.

하지만 이 조건만 만족한다면 자신감이 생긴 BOJ군은 무조건 표적을 맞출 수 있다.

여러분은 BOJ군의 코치가 되어 겨냥할 표적을 적절히 선택했을 때 얻을 수 있는 최대 점수를 구해주자.

첫 번째 줄에 $N$ 이 주어진다.

이후 $N$ 줄에 걸쳐 $i$ 번째 줄에는 $i$ 번째 과녁의 좌표 $(X\_i,Y\_i)$ 가 공백을 사이에 두고 주어진다.

한 줄에 겨냥할 표적을 적절히 선택했을 때 얻을 수 있는 최대 점수를 출력하라.