Sau màn bão tán của đêm livestream cực hot, DoMixi quyết định tổ chức một buổi fan-meeting hoành tráng không kém. Địa điểm? Một sân khấu hình vòng tròn cực xịn với ~n~ khu vực chỗ ngồi, đánh số theo chiều kim đồng hồ từ ~1~ đến ~n~ xung quanh vòng.

DoMixi muốn khu vực thứ ~i~ có đúng ~r_i~ fan ngồi vào. Để kiểm soát an ninh, ban tổ chức chỉ mở ~k~ trong số ~n~ cổng vào. Mỗi fan vào từ một cổng được mở rồi đi theo chiều kim đồng hồ đến khu vực của mình — dù sao thì đi thêm một chút cũng để ngắm DoMixi lâu hơn mà!

Fan có thể xếp hàng bên ngoài các cổng theo thứ tự tùy ý, nhưng sau khi vào cổng thì chỉ được đi theo chiều kim đồng hồ.

Hãy giúp DoMixi chọn ~k~ cổng cần mở sao cho tổng số bước đi của tất cả mọi người là nhỏ nhất nhé!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~3 \le n \le 100~, ~1 \le k \le 7~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~r_i~ (~1 \le r_i \le 10^6~) — số fan cần ngồi ở khu vực ~i~.

Kết quả

In ra một số nguyên duy nhất — tổng số bước đi tối thiểu.

Ví dụ

Đầu vào:

6 2
2
5
4
2
6
2

Đầu ra:

14

Giải thích: DoMixi mở cổng ~2~ và cổng ~5~. ~11~ fan vào từ cổng ~2~ đi tổng cộng ~8~ bước để vào khu vực ~2~, ~3~, ~4~. ~10~ fan vào từ cổng ~5~ đi tổng cộng ~6~ bước để vào khu vực ~5~, ~6~, ~1~.

Giới hạn

Trong tất cả các test: ~3 \le n \le 100~, ~1 \le k \le 7~, ~1 \le r_i \le 10^6~.

All in vào a Liêm thành công, Per sẽ sử dụng tiền thắng cược để trả nợ.

Hiện tại, Per đang nợ ~n~ người. Số tiền nợ biểu diễn bởi mảng ~a~ — Per nợ người thứ ~i~ một lượng tiền là ~a_i~. Nhà cái trả tiền thắng cược cho Per ~m~ đồng tiền, mệnh giá được biểu diễn bởi mảng ~b~ — đồng thứ ~i~ có giá trị ~b_i~.

Per muốn trả một lần hết sạch nợ. Nhưng đang tự hỏi xem liệu có tồn tại cách trả nợ nào hết ~n~ người không? Per rất muốn các bạn giúp Per trả lời câu hỏi này.

Lưu ý rằng mỗi đồng tiền chỉ sử dụng một lần (tức trả người này rồi thì không thể trả người kia tờ tiền này).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 5~) — số lượng bộ test cần xử lý.

Dòng đầu tiên của mỗi test chứa hai số nguyên ~n~, ~m~ (~1 \le n, m \le 20~) — số lượng người mà Per nợ và số lượng tờ tiền Per có.

Dòng thứ hai của mỗi test chứa ~n~ số nguyên ~a_i~ (~1 \le a_i \le 1000~) — số tiền mà Per nợ từng người.

Dòng thứ ba của mỗi test chứa ~m~ số nguyên ~b_i~ (~1 \le b_i \le 1000~) — mệnh giá của từng tờ tiền Per có.

Kết quả

Với mỗi bộ test, in ra YES nếu tồn tại cách trả hết nợ cho tất cả ~n~ người, ngược lại in ra NO.

Ví dụ

Đầu vào:

2
1 5
8
4 2 5 1 3
2 6
9 10
5 4 8 6 3 11

Đầu ra:

YES
NO

Giải thích:

• Test ~1~: Per có thể trả cho người ~1~ bằng cách chọn tờ tiền vị trí ~(3, 5)~ hoặc ~(1, 4, 5)~, ...
• Test ~2~: Per có thể trả cho người ~1~ bằng cách chọn tờ tiền vị trí ~(1, 2)~ hoặc ~(4, 5)~, nhưng không tìm được cách trả đồng thời cho người thứ ~2~. Do đó, không thể trả hết nợ cho cả ~n~ người.

Giới hạn

Trong tất cả các test: ~1 \le t \le 5~, ~1 \le n, m \le 20~, ~1 \le a_i, b_i \le 1000~.

Per đang có ~1~ gói kẹo và ~n~ lá bài. Mỗi lá bài được ghi số ~p_i~ trên đó. Trong lúc ăn kẹo, Per nghĩ ra một bài toán thú vị như sau:

Dùng dây nối hai lá ~i, j~ thì sẽ ăn ~\min(X, Y)~ cái kẹo, trong đó ~X = p_i \mod p_j~, ~Y = p_j \mod p_i~.

Per muốn nối các lá bài lại sao cho tất cả các lá đều được kết nối với nhau.

Per sợ sâu răng nên muốn ăn ít kẹo nhất có thể mà vẫn có thể kết nối ~n~ lá với nhau được. Các bạn hãy thử tìm cách giúp Per nhé!

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~) — số lượng lá bài.

Dòng tiếp theo chứa ~n~ số nguyên ~p_i~ (~1 \le p_i \le 10^7~) — giá trị lá bài thứ ~i~.

Kết quả

In ra một số nguyên duy nhất — số kẹo tối thiểu Per phải ăn để có thể kết nối ~n~ lá bài với nhau.

Ví dụ

Đầu vào 1:

4
2 6 3 11

Đầu ra 1:

1

Đầu vào 2:

3
4 9 15

Đầu ra 2:

4

Giải thích: Ở test đầu tiên, Per sẽ kết nối lá ~1~ và ~2~ với nhau và ăn ~0~ cái kẹo, kết nối lá ~2~ và ~3~ và ăn ~0~ cái kẹo, kết nối lá ~1~ và ~4~ và ăn ~1~ cái kẹo. Cả ~4~ lá đã được kết nối. Tổng số kẹo ăn là ~1~ — đây là đáp án tối thiểu.

Giới hạn

Trong tất cả các test: ~1 \le n \le 10^5~, ~1 \le p_i \le 10^7~.