만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이상한 격자

면접 대비

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

요약
방향마다 이동 비용이 다른 격자에서 N명의 사람이 한 칸에 모이는 데 드는 체력의 최솟값을 구합니다.
난이도

보통10점 중 5점

유형
정렬, 누적 합, 수학
정답자
아직 제출이 없습니다

문제

이상한 격자에서는 인접한 칸으로 이동할 때마다 체력이 소모된다. (x,y)(x, y)에서 (x−1,y)(x - 1, y)로 이동하면 AA, (x+1,y)(x + 1, y)로 이동하면 BB, (x,y−1)(x, y - 1)로 이동하면 CC, (x,y+1)(x, y + 1)로 이동하면 DD만큼의 체력이 소모된다.

NN명의 사람이 격자에 흩어져 있다. 이 사람들이 한 점에 모이기 위해 소모해야 하는 체력의 합의 최솟값은 얼마인가?

입력

첫 번째 줄에 NN, AA, BB, CC, DD가 차례대로 주어진다. (1≤N≤200 0001 \le N \le 200\,000, 0≤A,B,C,D≤1060 \le A, B, C, D \le 10^6)

두 번째 줄부터 NN개의 줄에 걸쳐 격자에서의 각 사람의 정수 좌표 XiX_i, YiY_i가 순서대로 주어진다. (−106≤Xi,Yi≤106-10^6 \le X_i, Y_i \le 10^6)

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 답을 출력한다.

예제1

  1. 예제 1

    입력
    3 2 1 1 2
    1 0
    0 3
    3 3
    
    예상 출력
    11