Phân bố sách

Có một tủ sách gồm $n$ ngăn. Ngăn thứ $i$ đang chứa $a_i$ quyển sách. Bạn muốn mỗi ngăn chứa không quá $k$ quyển sách.

Để đạt được mục tiêu, bạn có thể thực hiện hai loại thao tác sau (mỗi loại có thể dùng nhiều lần, theo thứ tự tùy ý):

1. Chọn đúng một ngăn và chuyển toàn bộ sách của ngăn đó vào kho (tức gán $a_i:=0$). Mỗi lần thực hiện tốn $x$ giây.
2. Lấy toàn bộ sách trên cả $n$ ngăn rồi phân bố lại đều giữa $n$ ngăn. Mỗi lần thực hiện tốn $y$ giây.

Với một dãy $a$ gồm $n$ số, phân bố đều là một dãy $b$ gồm $n$ số sao cho tổng của $b$ bằng tổng của $a$ và giá trị $max(b)-min(b)$ nhỏ nhất có thể. Ví dụ, nếu $a=[5,4,3]$ thì phân bố đều là $b=[4,4,4]$; nếu $a=[1,2,3,4]$ thì phân bố đều là $b=[2,3,3,2]$ (hoặc một hoán vị bất kỳ của dãy này).

Hãy tìm tổng số giây ít nhất cần bỏ ra để mỗi ngăn chứa không quá $k$ quyển sách.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$: số lượng test.
• Với mỗi test:
  • Dòng thứ nhất chứa bốn số nguyên $n$, $k$, $x$, $y$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi test, in ra một số nguyên: số giây ít nhất cần bỏ ra.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le k\le n\le 2·{10}^5$
• $1\le x,y\le {10}^4$
• $1\le a_i\le n$
• Tổng $n$ trên tất cả các test không vượt quá $2·{10}^5$.

Ví dụ