시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3112939.130%

문제

HI-ARC Games의 신작 게임 "돈 피하지 않기"가 출시되었다. 이 게임은 흔히 "똥 피하기"라고 알려진 게임과 유사하지만, 모든 똥을 피해야 하는 "똥 피하기"와 다르게 "돈 피하지 않기"는 모든 돈을 모아야 한다. 게임은 각 칸을 $(x, y)$로 나타내는 $2$차원 격자에서 진행된다. 그린은 초기에 $(0, 0)$ 칸에 위치해 있으며, $y < 0$인 칸들은 전부 땅이다.

←키와 →키를 눌러서 땅 위($y=0$)에서 그린을 각각 좌, 우로 움직일 수 있으며, ↑키를 이용하면 점프를 하여 잠시 $y=1$까지 올라갈 수 있다. 그린은 일정한 속도로 아래로 떨어지는 $N$개의 돈을 하나도 빠짐없이 모아야 한다. 돈은 땅을 뚫고 내려가므로, 땅 아래 ($y < 0$)까지 도달하게 된다면 그 돈을 먹을 방법이 없어지므로 게임오버이다.

돈은 매초마다 아래로 한 칸 움직이며, 그린은 매초 플레이어가 어떤 키를 누르느냐에 따라 위의 그림과 같이 움직인다. 반투명한 캐릭터가 그려진 칸이 $t-1$초에 마지막으로 방문한 칸이라면, $t$초에는 화살표를 따라 차례대로 칸을 방문한다. "!"가 그려진 칸이 $t$초에 마지막으로 방문하게 되는 칸이다. (자세한 정의는 하단의 [노트]에 나와 있다.)

만약 돈이 움직여 도착한 칸을 그린이 같은 초에 방문한다면, 그 돈을 얻을 수 있다.

예를 들어 $t-1$초에 그린은 $(0,0)$에 있고, $5$개의 돈이 각각 $(0,1), (0,2), (1,0), (1,1), (1,2)$에 있다고 해보자. 만약 →키 + ↑키를 누른다면, $t$초에 $(1,1)$로 이동하는 $5$번째 돈과 $(1, 0)$으로 이동하는 $4$번째 돈을 수집할 수 있다. 이때 $(0,0)$은 그린이 $t-1$초에 방문했었던 칸이지, $t$초에 방문한 칸이 아니므로 $1$번째 돈은 모을 수 없다. 반면에 ↑키만 눌렀거나 아무 키도 누르지 않았다면, 방문하는 칸에 $(0, 0)$이 포함되어 있기 때문에 $1$번째 돈을 모을 수 있다.

이 게임의 모든 룰의 파악한 연두는 드디어 게임을 플레이해 보려고 한다. 하지만, 백준 랭작을 너무 많이 해서 손가락 관절이 좋지 않은 연두는 최소한의 힘만을 이용해서 이 게임에서 승리하고자 한다. ←키나 →키를 한번 누르는 것은 $P_{lr}$의 힘이, ↑키를 한번 누르는 것은 $P_j$의 힘이 소모된다. 모든 돈을 모아 게임에서 승리하기 위해, 힘을 최소 얼마나 소모해야 할지 구해보자.

입력

첫째 줄에 $N$, $P_{lr}$, $P_j$가 주어진다. ($1 \le N, P_{lr}, P_j \le 10^5$)

다음 $N$개의 줄에, $i$번째 돈의 초기 위치 $x_i$와 $y_i$가 주어진다. 모든 돈의 초기 위치는 다르다. ($-10^9 \le x_i \le 10^9, 1 \le y_i \le 10^9$)

입력에서 주어지는 모든 수는 정수이다.

출력

$N$개의 돈을 모두 모으는 것이 가능하다면, 그때 소모되는 힘의 합의 최솟값을 출력한다.

$N$개의 돈을 모두 모으는 것이 불가능하다면, 대신 $-1$을 출력한다.

예제 입력 1

6 3 5
1 2
1 4
-1 7
2 9
2 12
0 13

예제 출력 1

34

매초마다 다음과 같은 순서로 키를 누르면 $34$의 힘이 소모된다. "X"는 아무 키도 누르지 않았음을 의미한다 : (X), (→), (X), (X), (←), (←+↑), (→), (→), (→), (X), (↑), (←), (←)

예제 입력 2

4 100000 1
100000 100001
100000 100002
100001 100001
100001 100002

예제 출력 2

10000200002

예제 입력 3

2 1 1
1 1
-1 1

예제 출력 3

-1

예제 입력 4

2 5 5
0 1
5 5

예제 출력 4

-1

노트

  • $0$초에 각 돈은 입력에서 주어진 초기 위치에 존재하며, 그린은 $(0, 0)$을 방문한다.
  • $t (t>0)$초에 돈과 그린은 다음과 같이 움직인다.
    • $t-1$초에 $(x, y)$에 위치했던 돈은, $t$초에 $(x, y-1)$에 위치한다.
    • $t-1$초에 마지막으로 그린이 방문한 칸이 $(x, 0)$이라면, 어떤 키를 누르냐에 따라 $t$초에 다음과 같은 칸을 순서대로 방문한다.
      • 누른 키 방문하는 칸 (순서대로) 소모되는 힘
        ←키 $(x-1, 0)$ $P_{lr}$
        아무 키도 누르지 않음 $(x, 0)$ $0$
        →키 $(x+1, 0)$ $P_{lr}$
        ←키 + ↑키 $(x-1, 1) \rightarrow (x-1, 0)$ $P_{lr}$ + $P_{j}$
        ↑키 $(x, 1) \rightarrow (x,0)$ $P_{j}$
        →키 + ↑키 $(x+1, 1) \rightarrow (x+1, 0)$ $P_{lr}$ + $P_{j}$
  • $t$초에 어떤 돈이 위치하는 칸을, $t$초에 그린이 방문하게 된다면 그 돈을 모을 수 있다.

출처

University > 홍익대학교 > 2022 홍익대학교 HI-ARC 프로그래밍 경진대회 G번