Chi phí tối thiểu

Cho một lưới gồm $n$ hàng (đánh số từ $1$ đến $n$) và ${10}^6+2$ cột (đánh số từ $0$ đến ${10}^6+1$). Ô ở hàng $i$, cột $j$ được ký hiệu là $(i,j)$. Hai ô kề cạnh (chung cạnh) được nối với nhau bằng một cạnh.

Ban đầu, mỗi hàng $i$ có đúng một chướng ngại vật đặt tại ô $(i,a_i)$.

Bạn muốn di chuyển một số chướng ngại vật sao cho tồn tại đường đi từ ô $(1,0)$ đến ô $(n,{10}^6+1)$ theo các cạnh của lưới mà không đi qua ô chứa chướng ngại vật. Chi phí di chuyển chướng ngại vật như sau:

• Tốn $u$ đồng để di chuyển một chướng ngại vật từ ô $(i,j)$ sang ô $(i-1,j)$ hoặc $(i+1,j)$ (di chuyển dọc), nếu ô đích tồn tại và hiện không chứa chướng ngại vật.
• Tốn $v$ đồng để di chuyển một chướng ngại vật từ ô $(i,j)$ sang ô $(i,j-1)$ hoặc $(i,j+1)$ (di chuyển ngang), nếu ô đích tồn tại và hiện không chứa chướng ngại vật.

Không được di chuyển chướng ngại vật ra ngoài lưới. Hãy tính số đồng ít nhất cần chi để có thể đi từ $(1,0)$ đến $(n,{10}^6+1)$. Có thể chứng minh rằng với các ràng buộc của bài toán, luôn tồn tại cách làm cho hành trình khả thi.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le {10}^4$): số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng đầu chứa ba số nguyên $n$, $u$, $v$ ($2\le n\le 100$, $1\le u,v\le {10}^9$): số hàng của lưới và chi phí di chuyển dọc, ngang.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^6$): vị trí cột của chướng ngại vật ở từng hàng.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên: số đồng ít nhất cần chi.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le 100$, tổng $n$ trên tất cả bộ dữ liệu không vượt quá $2·{10}^4$
• $1\le u,v\le {10}^9$
• $1\le a_i\le {10}^6$

Ví dụ