Informatica Online Judge

  Rook(룩) [0768 / 0300]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 42   Total Tried : 117


The Champion of this Problem (C++) : gs16017 - ms / 924byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

서양 장기인 체스(Chess)는 아래와 같은 형태의 판에서 게임을 진행한다.

실제 체스판은 8*8로 구성되어 있지만 이 문제에서는 매우 큰 가상의 체스판의 문제로 가정한다. 다음 [그림-1]은 이 문제에서 이용될 체스판이다.






[그림-1]





이 체스판의 좌표는 x, y 두 축으로 구성되며 그 값은 -1억~1억까지이다.

체스의 말 중에 ROOK이라는 말이 있다. ROOK는 아래 [그림-2]와 같이 상,하,좌,우에 있는 말은 어느 것이든 공격할 수 있다.





                            
[그림-2]                                                                           [그림-3]





이 문제에서는 N개의 ROOK가 서로 공격할 수 없는 위치에 배치된 상태로 시작된다.

이 N개의 ROOK들 중 하나를 선택하면 [그림-3]과 같이 4개의 사분면으로 다른 ROOK들이 나뉘게 된다.

한 ROOK을 정하게 되면 점수를 받게 된다. 점수는 다음과 같이 계산한다.









여러분은 주어진 N개의 ROOK들 중 가장 높은 점수를 얻을 수 있는 ROOK을 택하여 그 점수를 구하는 프로그램을 작성하면 된다.

Input

첫 번째 줄에 ROOK의 수 N이 주어진다. (단, N은 100,000이하의 자연수)
두 번째 줄에 각 사분면의 점수가 공백으로 구분되어 입력된다.
세 번째 줄부터 N줄에 걸쳐서 각 ROOK의 x, y좌표가 공백으로 구분되어 입력된다.
(각 좌표의 절댓값은 1억을 초과하지 않는다.)

Output

얻을 수 있는 최대 점수를 출력한다. (출력값은 32bit정수형을 초과하지 않는다.)

IO 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점이된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]