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 \cdot 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 \cdot (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, ..., 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.

Input

Đọc từ thiết bị vào chuẩn:

• 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 \cdot 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.

Output

Ghi ra thiết bị ra chuẩn ~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. Đá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.

Scoring

Sample Input 1

1
7 2
7 8
11 7 12 6 3 7 10

Sample Output 1

80.000000000

Gia đình của Nam được bầu chọn là hộ canh tác xuất sắc nhất năm do sản lượng canh tác thu được hiệu quả nhất trên thửa ruộng được phân chia. Năm nay chính quyền địa phương lại tiếp tục phân chia cho các hộ gia đình trên một cánh đồng hình chữ nhật có chứa nhiều ao nhỏ bên trong. Các ao này có thể chia thành nhiều mảnh ao hình chữ nhật tùy theo mục đích sử dụng của các hộ gia đình. Để thưởng cho thành tích canh tác ấn tượng năm trước, chính quyền địa phương ưu tiên quyền chọn đầu tiên cho gia đình Nam một thửa ruộng hình chữ nhật con trên cánh đồng. Thửa ruộng này cần thỏa mãn chứa không quá ~2~ mảnh ao hình chữ nhật không giao nhau ngoại trừ có thể có chung cạnh.

Cánh đồng được biểu diễn bởi một ma trận ~A~ gồm ~n~ hàng ~m~ cột, ô ~(i,j)~ nhận giá trị ~A_{i,j}~ bằng ~0~ hoặc ~1~, ~A_{i,j}~ ~=~ ~0~ nghĩa là ô đó thuộc vùng ao, còn ~A_{i,j}~ ~=~ ~1~ ngược lại. Như vậy, mỗi mảnh ao hình chữ nhật tương ứng với một ma trận con của ~A~ có tất cả các phần tử đều là ~0~, gọi là ma trận ~0~. Một thửa ruộng con hình chữ nhật trên cánh đồng tương ứng với một ma trận con của ~A~ với các phần tử có giá trị ~1~ hoặc ~0~, giá trị sử dụng của thửa ruộng đó bằng tổng giá trị các phần tử trong ma trận con tương ứng. Thửa ruộng của gia đình Nam cần thỏa mãn là tồn tại một cách tạo thành không quá ~2~ ma trận ~0~ không có phần tử chung từ tất cả các phần tử ~0~ trong ma trận con biểu diễn thửa ruộng đó. Gia đình Nam mong muốn tìm được thửa ruộng có giá trị sử dụng lớn nhất có thể.

Yêu cầu: Cho biết ma trận ~A~, hãy giúp gia đình Nam tìm được ma trận con của ~A~ có tổng giá trị phần tử lớn nhất mà tồn tại một cách tạo thành không quá ~2~ ma trận ~0~ không có phần tử chung từ tất cả các phần tử ~0~ trong đó.

Input

• Dòng đầu chứa hai số nguyên dương ~n,m~ cách nhau bởi dấu cách ~(n,m \le 5000)~.

• Mỗi dòng trong số ~n~ dòng tiếp theo chứa ~m~ số ~A_{i,j}~ có giá trị ~0~ hoặc ~1~ viết liên tiếp nhau.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng giá trị các phần tử của ma trận con tìm được.

Scoring

Sample Input 1

5 5
10101
11000
11111
11111
00100

Sample Output 1

12

Sample Input 2

5 7
1000000
0101110
0100110
0100001
0110010

Sample Output 2

7

Notes

Hình vẽ minh họa ví dụ ~1~:

Giải thích ví dụ ~1~: Đáp án cho ma trận con có giá trị sử dụng lớn nhất là chọn ma trận con từ hàng ~2~ đến hàng ~3~ và từ cột ~2~ đến cột ~6~. Tất cả các phần tử ~0~ trong đó có thể tạo thành hai ma trận ~0~ không có phần tử chung là:

• Ma trận ~0~ thứ nhất là ma trận một cột từ hàng ~2~ đến hàng ~3~ của cột ~3~;

• Ma trận ~0~ thứ hai là ma trận một phần tử hàng ~3~ cột ~4~.

Hình vẽ minh họa ví dụ ~2~:

Giải thích ví dụ ~2~: Đáp án cho ma trận con có giá trị sử dụng lớn nhất là chọn ma trận con từ hàng ~2~ đến hàng ~4~ và từ cột ~1~ đến cột ~5~. Tất cả các phần tử ~0~ trong đó có thể tạo được đúng một ma trận ~0~ không có phần tử chung là ma trận một hàng từ cột ~3~ đến cột ~5~ của hàng ~2~.

Công ty xổ số Lottery vừa ra mắt một mô hình xổ số mới. Ban đầu họ chọn và công bố hai số nguyên dương ~n~ và ~k~. Một xâu nhị phân ~s~ có độ dài ~n~ được chọn để làm giải độc đắc và được giữ bí mật. Hình thức bán vé của công ty là cho phép người chơi chọn số nhị phân (hoặc ~0~ hoặc ~1~) ở một số vị trí trong số ~n~ vị trí trên tấm vé và bỏ trống các vị trí còn lại. Tấm vé sau đó được in ra có mã số là một xâu có độ dài ~n~ và chỉ chứa các kí tự '0', '1', '*' mô tả các vị trí bỏ trống. Việc bỏ trống một số vị trí sẽ tăng khả năng trùng khớp với giải độc đắc, tuy nhiên, cũng làm tăng giá của tấm vé số lên. Cụ thể, giá của một tấm vé có mã số ~t~ được tính như sau:

• Gọi ~a~, ~b~, ~c~ lần lượt là số lượng kí tự '0', '1', '*' trên xâu ~t~;

• Giá của tấm vé sẽ là ~a + b + 2c~;

và độ trùng khớp của tấm vé này với giải độc đắc được tính như sau:

• Đánh số các kí tự trên ~s~ từ ~0~ đến ~n - 1~ từ trái sang phải;

• Đánh số các kí tự trên ~t~ từ ~0~ đến ~n - 1~ từ trái sang phải;

• ~s~ và ~t~ được gọi là ~k~-khớp ở vị trí ~i~ (~0 \le i < n~) nếu với mọi ~j~ (~0 \le j < k~) ta có ~s_{(i + j) \% n} = t_{(i + j) \% n}~ hoặc ~t_{(i + j) \% n} =~'*';

• Độ trùng khớp của tấm vé này với giải độc đắc sẽ là số lượng vị trí ~k~-khớp của ~s~ và ~t~.

Khi mua một tấm vé có mã số ~t~, bạn sẽ nhận được thông tin về độ trùng khớp của tấm vé này với giải độc đắc. Nếu độ trùng khớp bằng ~n~ và xâu ~t~ không chứa kí tự '*' nào thì bạn mới trúng giải độc đắc.

Yêu cầu: Bạn được phép mua vé nhiều lần, mỗi lần một vé, hãy sử dụng càng ít tiền càng tốt để mua và trúng được giải độc đắc.

Input

Thí sinh cần cài đặt hàm void run(int n, int k) đặt trong file lotte.cpp. Trong file lotte.cpp thí sinh cần phải khai báo thư viện bằng dòng lệnh #include "lottelib.h" (xem thêm các file mẫu trong mục đính kèm trên hệ thống để hiểu hơn về cách tương tác với hệ thống, các file này chỉ để thí sinh hiểu cách thức tương tác, không phải dùng để chấm bài).

Trong hàm run, mỗi lần mua vé bạn cần gọi hàm int buy(string t) với ~t~ là một xâu độ dài ~n~ chỉ chứa các kí tự '0', '1', '*' là mã của tấm vé bạn muốn mua (hàm này được cung cấp trong thư viện lotte.h. Hàm sẽ trả về độ trùng khớp của tấm vé này với giải độc đắc.

Chương trình sẽ tự động kết thúc nếu như một trong các tình huống sau xảy ra:

• Bạn mua được tấm vé trúng giải độc đắc;

• Tham số ~t~ truyền vào hàm buy là không hợp lệ;

• Chương trình của bạn sinh lỗi hoặc chạy quá thời gian quy định.

Output

Scoring

Có tất cả ~3~ subtask. Với mỗi test trong một subtask, cách tính ~\%~ điểm như sau:

• Nếu bạn trúng giải độc đắc, gọi ~T~ là tổng số tiền đã sử dụng, điểm của test đó là:

  • ~100\%~ số điểm nếu ~T < 0.75n^2~;

  • ~100\% \times \dfrac{1.1n^2 - T}{0.35n^2}~ số điểm nếu ~0.75n^2 \le T \le 1.1n^2~;

  • ~0\%~ số điểm nếu ~1.1n^2 < T~.

• Ngược lại, bạn được ~0~ điểm cho test đó.

Với mỗi subtask, gọi ~e~ là ~\%~ điểm nhỏ nhất mà thí sinh đạt được trong các test, ~score~ là điểm của subtask, khi đó điểm cho subtask được tính bằng ~e \times score~.

Notes

Với ~s =~"10111", ~n = 5~, ~k = 2~, hàm run sẽ được gọi với giá trị các tham số tương ứng là run(5,2), dưới đây là một ví dụ cách gọi lần lượt các hàm buy cho phép bạn trúng giải độc đắc: