Problems
서양 장기인 체스(Chess)는 아래와 같은 형태의 판에서 게임을 진행한다.
실제 체스판은 8*8로 구성되어 있지만 이 문제에서는 매우 큰 가상의 체스판의 문제로 가정한다. 다음 [그림-1]은 이 문제에서 이용될 체스판이다.
[그림-1]
이 체스판의 좌표는 x, y 두 축으로 구성되며 그 값은 -1억~1억까지이다.
체스의 말 중에 ROOK이라는 말이 있다. ROOK는 아래 [그림-2]와 같이 상,하,좌,우에 있는 말은 어느 것이든 공격할 수 있다.
[그림-2]
[그림-3]
N개의 ROOK들 중 하나를 선택하면 선택한 ROOK이 공격할 수 없는 다른 ROOK들은 [그림-3]과 같이 4개의 사분면으로 나뉘게 된다.
한 ROOK을 정하게 되면 공격받지 않는 ROOK들에 대해서 점수를 받게 된다. 점수는 다음과 같이 계산한다.
여러분은 주어진 N개의 ROOK들 중 가장 높은 점수를 얻을 수 있는 ROOK을 택하여 그 점수를 구하는 프로그램을 작성하면 된다.
Input
첫 번째 줄에 ROOK의 수 N이 주어진다. (단, N은 100,000이하의 자연수)
두 번째 줄에 각 사분면의 점수가 공백으로 구분되어 입력된다.
세 번째 줄부터 N줄에 걸쳐서 각 ROOK의 x, y좌표가 공백으로 구분되어 입력된다.
(각 좌표의 절댓값은 1억을 초과하지 않는다.)
Output
얻을 수 있는 최대 점수를 출력한다. (출력값은 32bit정수형을 초과하지 않는다.)
Example
4
2 -1 3 1
0 0
-1 -2
-2 -1
2 1
9
[그림-3]과 같이 0,0의 ROOK를 택하면 1사분면에 1개, 3사분면에 2개 즉 2*1 + 3*2 = 8이 되어 8점을 획득하지만 (2,1)에 있는 ROOK를 선택하면 3사분면에 3개가 존재하여 3*3 = 9이다. 따라서 얻을 수 있는 최대 점수는 9점이된다.
You must sign in to write code.