돈 피하지 않기 게임

문제

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$ 을 출력한다.

힌트

$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$ 초에 그린이 방문하게 된다면 그 돈을 모을 수 있다.