Chia ruộng

Một cánh đồng lúa hình chữ nhật có kích thước chiều dọc là $L$ và chiều ngang là $W$ cần được đào $m$ đường mương khác nhau chạy song song với cạnh chiều ngang nối hai cạnh chiều dọc của cánh đồng nhằm phục vụ hiệu quả cho việc tưới tiêu canh tác. Các đường mương này chia cánh đồng theo chiều dọc thành $(m+1)$ lớp có diện tích dương. Trong bài toán này, chúng ta coi mỗi đường mương có bề rộng không đáng kể.

Chính quyền địa phương tìm các phân chia cánh đồng lúa cho $n$ hộ gia đình quản lý canh tác, hộ gia đình thứ $i$ được chia một thửa ruộng hình chữ nhật con nằm trong một lớp có hai cạnh thuộc đường mương hoặc cạnh chiều ngang của cánh đồng, và có diện tích định trước $a_i$ sao cho $\sum a_i=L·W$. Gọi $l_i$ và $w_i$ lần lượt là kích thước chiều dọc và chiều ngang thửa ruộng của hộ gia đình thứ $i$, chu vi thửa ruộng là $p_i=2·(l_i+w_i)$. Chính quyền địa phương mong muốn tìm ra phương án phân chia sao cho tổng chu vi tất cả các thửa ruộng con $\sum p_i$ là nhỏ nhất.

Yêu cầu: Cho biết kích thước chiều dọc $L$ và chiều ngang $W$ của cánh đồng lúa hình chữ nhật, số lượng mương cần đào và $n$ giá trị diện tích $a_1,a_2,\dots ,a_n$. Hãy giúp chính quyền địa phương tìm ra phương án phân chia mong muốn và đưa ra giá trị tổng chu vi nhỏ nhất của tất cả các thửa ruộng con.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương $T$ là số lượng bộ test $(T\le 3)$.

Mỗi nhóm dòng trong số $T$ nhóm dòng tiếp theo mô tả một bộ test có cấu trúc như sau:

• Dòng thứ nhất chứa hai số nguyên không âm $n$ và $m$ $(m<n\le 25000)$.
• Dòng thứ hai chứa hai số nguyên không âm $L$ và $W$ $(L,W\le {10}^9)$.
• Dòng cuối cùng chứa $n$ số nguyên dương $a_i$ $(a_i\le {10}^9,1\le i\le n)$. Dữ liệu đảm bảo $\sum a_i=L·W$.

Hai số liên tiếp trong cùng một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng một số thực duy nhất là tổng chu vi tính được trong bộ test tương ứng và có tối đa $9$ chữ số sau dấu chấm thập phân (viết ở dạng thập phân thông thường, không dùng dạng lũy thừa như 1e+13). Đáp án của bạn được phép có sai số tuyệt đối đến ${10}^{-3}$ so với đáp án trong bộ test.

Ràng buộc

• $1\le T\le 3$.
• $0\le m<n\le 25000$.
• $0\le L,W\le {10}^9$.
• $1\le a_i\le {10}^9$, $\sum a_i=L·W$.

Subtasks

• Subtask 1 ($12\%$ số điểm): $m,n\le 15$.
• Subtask 2 ($28\%$ số điểm): $m,n\le 500$.
• Subtask 3 ($26\%$ số điểm): $m,n\le 4000$.
• Subtask 4 ($34\%$ số điểm): $m,n\le 25000$.

Ví dụ