사다리 게임

사다리 게임에 쓰이는 사다리가 있다. 세로선은 N개, 가로선은 M개이다. 세로선은 왼쪽부터 1, 2, ..., N번이고, 가로선은 위에서부터 1, 2, ..., M번이다. 같은 높이에 있는 가로선은 없다.

맨 위의 a번 위치에서 출발하면 사다리를 따라 아래로 내려간다. 내려가다가 가로선을 만나면 그 가로선이 연결한 옆 세로선으로 이동한다.

사다리를 원하는 결과가 나오도록 바꿀 수 있다. 기존 가로선 하나를 지우는 데는 X, 새 가로선 하나를 그리는 데는 Y의 비용이 든다. 새 가로선은 서로 이웃한 두 세로선을 연결하며 필요한 위치에 그릴 수 있다.

맨 위 a번 위치에서 출발한 경로가 맨 아래 b번 위치에 도착하도록 사다리를 바꾸는 최소 비용을 구하라.

첫째 줄에 N과 M(1 <= N <= 100, 0 <= M <= 500)이 주어진다.

다음 줄에 a, b, X, Y(0 <= X, Y <= 1,000)가 주어진다.

다음 M개의 줄에는 위에서부터 각 가로선의 정보를 나타내는 정수 p가 하나씩 주어진다. 이는 p번 세로선과 p+1번 세로선을 연결하는 가로선을 뜻한다.

최소 비용을 출력한다.