막대 자르기

Albert는 공작소를 운영한다. 오늘은 고객이 $N$개의 공작용 나무 막대를 가져왔는데 $i$번째 막대의 길이를 $S\_i$라 하자. 고객은 길이가 $1$인 막대가 총 $K$개 필요한데, 자신이 가져온 막대를 필요한만큼 적절히 잘라주기 바란다. 이 공작용 막대는 특수 기계를 이용해서만 자를 수 있는데, 길이가 $L \ge 2$ 인 막대를 넣으면 아주 정밀하게 $L$개의 길이 $1$인 막대로 잘라주는 대신 길이에 비례하여 큰 비용이 발생한다. 구체적으로, 길이가 $L$인 막대를 넣으면 발생하는 비용은 $a \cdot (L - 1)^2 + b$ 이고 $a, b \ge 0$ 이다.

예를 들어 $N = 3$, $K = 8$, $S = \[8, 4, 4]$, $a = 1$, $b = 0$ 이라 하자.

• 모든 막대를 다 자르면 총 16개의 길이 1짜리 막대를 얻을 수 있고, 비용은 $7^2 + 3^2 + 3^2 = 67$ 이다 - 이 방법은 고객의 요구를 만족시키긴 하지만 가장 비싼 방법이다.
• 길이가 8인 막대 하나만 자르면 총 8개의 길이 1짜리 막대를 얻을 수 있고, 비용은 49이다.
• 길이가 4인 막대 두 개를 자르면 총 8개의 길이 1짜리 막대를 얻을 수 있고, 비용은 18이다 - 이 방법이 가장 싼 방법이다.

다른 예로 $N = 4$, $K = 9$, $S = \[3, 4, 5, 6]$, $a = 1$, $b = 0$ 이라 하자.

• 모든 막대를 다 자르면 고객의 요구를 만족시키지만 비용이 $2^2 + 3^2 + 4^2 + 5^2 = 54$로 가장 비싸다.
• 길이가 3인 막대와 6인 막대를 자르면 $2^2 + 5^2 = 29$의 비용을 내고 총 9개의 막대를 얻을 수 있다.
• 길이가 4인 막대와 5인 막대를 자르면 $3^2 + 4^2 = 25$의 비용을 내고 총 9개의 막대를 얻을 수 있다.

입력으로 $N$, $K$, $a$, $b$, 그리고 $S$가 주어졌을 때, $K$개 이상의 길이 1인 막대기를 얻기 위해 최소로 필요한 비용을 계산해보자.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$, $K$, $a$, $b$가 공백으로 구분되어 주어진다. 둘째 줄에는 막대기의 길이인 배열 $S$가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• $1 \le T \le 20$
• $1 \le N \le 100$
• $0 \le a, b \le 10^6$
• $1 \le i \le N$인 $i$에 대하여: $1 \le S\_i \le 100$
• $1 \le K \le \sum\_{i=1}^{N} S\_i$