27953번 - 공룡 게임 서브태스크

윤우는 41기 학생들을 너무 좋아해서, 자신이 좋아하는 게임을 이들에게 소개하고자 한다. 이름하여 그 유명한 "공룡 게임(DINOSAUR GAME)"이다. 그러나 41기 학생들은 "공룡 게임 따위는 재미없다"라면서, 윤우에게 싫증을 내었다. 이에 윤우는 41기 학생들에게 자신이 공룡 게임을 얼마나 잘하는지 보여줌으로써 41기 학생들에게 공룡 게임의 매력을 보여주려 했다. 그런데, 문제가 생겼다. 실력이 부족했던 윤우는 41기 학생들에게 자신이 죽는 모습만 보여줘서 오히려 역효과를 낼까봐 두려웠다. 이에 윤우는 '공룡 게임'에서 자신이 언제 점프하고 슬라이딩해야 하는지 미리 계산해 놓은 뒤, 이를 바탕으로 게임을 진행하여 41기 학생들에게 완벽한 모습을 보여주고자 했다.

이미 언급한 바와 같이 '공룡 게임'에는 두 가지 액션이 존재한다. 하나는 점프, 다른 하나는 슬라이딩이다. 각각의 장애물들은 적절한 액션을 취하여 넘을 수 있다. 장애물 1은 점프, 장애물 2는 슬라이딩으로만 넘을 수 있고, 장애물 3은 점프와 슬라이딩으로 모두 넘을 수 있다. 윤우의 '공룡 게임'에는 또 독특한 시스템이 하나 더 있다. 바로 점프와 슬라이딩에 각각 쿨타임이 존재한다는 것이다. 엄밀히 이야기하자면, 점프 쿨타임 $A$에 대하여 점프와 다음 점프 사이의 시간 차이가 $A$초 이상이어야 한다. 슬라이딩 쿨타임 $B$에 대해서도 마찬가지이다. 단 점프나 슬라이딩을 처음 할 시에는 쿨타임의 영향을 받지 아니한다.

또한 공룡이 점프를 하면 $X$만큼의 패널티를 받고, 슬라이딩을 하면 $Y$만큼의 패널티를 받는다. 장애물들의 종류와 그 장애물이 나타나는 시각이 주어질 때, 윤우가 모든 장애물을 넘기 위한 최소 패널티를 출력하라. 아 참! 윤우가 장애물들을 모두 통과할 수 있는지 없는지에 대한 여부도 출력해야 한다.

첫째 줄에 다섯 개의 정수 $N$, $A$, $B$, $X$, $Y$가 입력된다.

$N$은 장애물의 개수를 의미한다. $A$와 $B$는 각각 점프와 슬라이딩의 쿨타임을, $X$와 $Y$는 각각 점프와 슬라이딩의 패널티를 의미한다.

이후 $N$개의 줄에 걸쳐서 $T_i$와 $S_i$가 주어진다. $(1\leq i\leq N)$

$T_i$는 $i$번째 장애물이 나타나는 시각을, $S_i$는 $i$번째 장애물의 종류를 나타낸다. $(1\leq i\leq N)$

$S_i$가 1이면 점프로만 넘을 수 있는 장애물, 2이면 슬라이딩으로만 넘을 수 있는 장애물이며, 3일 때는 점프와 슬라이딩으로 모두 넘을 수 있는 장애물이다.

$T_i$는 오름차순으로 주어진다. 또한 한 시각에 여러 장애물이 존재하지 않는다. 즉, 모든 $1\leq i<j\leq N$ 에 대해, $T_i\neq T_j$이다.

첫째 줄에 윤우가 모든 장애물을 넘기 위한 최소 패널티를 출력한다.

만약 어떻게 액션을 취하더라도 모든 장애물을 넘을 수 없다면 -1을 출력한다.

• $1\leq N\leq 5,000$
• $1\leq A,B,X,Y,T_i\leq 1,000,000,000$ $(1\leq i\leq N)$
• $S_i\in\{1,2,3\}$ $(1\leq i\leq N)$
• $T_i < T_j$ ($1\leq i<j\leq N$)