Lúc em chạm môi anh ta em có ngần ngại?

Có ngần ngại không hay miên man nhớ mãi?

Trả lời đi hương nước hoa thơm mùi gì chen giữa chúng ta

Anh trao em con tim, sao em trao cho anh... MỘT CÚ LỪA

La la la la la la LỪA...

(Một Cú Lừa – Bích Phương)

Chắc nhiều bạn chưa biết, ngoài công việc chính là bán trà sữa dạo, GSPVH còn có một trại nuôi LỪA siêu to khổng lồ.

Sở dĩ GSPVH nuôi LỪA là bởi, để có thể hoàn thành tốt công việc ra đề thi và dạy học – thị trường tiêu thụ trà sữa chính của GS, thì ngoài việc nuôi gà, kỹ năng lùa LỪA cũng vô cùng quan trọng. Người ra đề thi phải biết lùa LỪA thì mới có thể đưa thí sinh vào bẫy, để ban giámkhảo có thể có những tràng cười sảng khoái khi chứng kiến bài làm của thí sinh. Hẳn nhiều thế hệ sinh viên Việt Nam không thể quên bài L đề ICPC quốc gia 2017 hay bài G đề ICPC quốc gia 2018 – những cú LỪA đã đi vào lịch sử. Và biết đâu, ngay trong chính mùa PVHOI 4.0 này cũng có một cú LỪA siêu kinh điển như thế...

Trở lại với trang trại LỪA của GSPVH, nhờ chịu khó chăm nuôi, tâm huyết với đàn, giờ đây đàn LỪA của GSPVH đã phát triển đông đảo với \(n\) con LỪA béo tốt, con LỪA thứ \(i\) có khối lượng là \(w_{i}\). Hôm nay, nhân ngày chủ nhật đầy nắng đẹp và gió mát, GSPVH quyết định dẫn đàn LỪA của mình đi chơi. GSPVH muốn dẫn đàn LỪA của mình sang bên kia sông, nơi có vườn hoa thơm ngát và tươi tắn. Nhưng vì kinh phí có hạn, GS chỉ thuê được một chiếc thuyền với tải trọng \(c\) (nói cách khác, chiếc thuyền này chỉ có thể chở được khối lượng không quá \(c\)).

GSPVH sẽ tự tay chèo thuyền từng chuyến để đưa đàn LỪA này qua sông. Với mong muốn đưa đàn LỪA qua sông nhanh nhất có thể, GSPVH sử dụng chiến lược tham lam như sau:

• Bước \(1\): GSPVH sắp xếp các con LỪA chưa qua sông theo thứ tự giảm dần về khối lượng.
• Bước \(2\): GSPVH lần lượt xét các con LỪA theo thứ tự vừa sắp xếp. Với mỗi con LỪA, nếu khối lượng của nó cộng với tổng khối lượng các con LỪA đang trên thuyền không quá tải trọng \(c\), GSPVH sẽ lập tức đưa con LỪA đó lên thuyền. Nói cách khác, GSPVH luôn ưu tiên đưa lên thuyền con LỪA có khối lượng lớn nhất có thể, đảm bảo rằng tổng khối lượng các con LỪA được đưa lên thuyền không vượt quá giới hạn khối lượng \(c\) của thuyền.
• Bước \(3\): GSPVH lái thuyền qua bên kia bờ sông và đưa các còn LỪA trên thuyền lên bờ.
• Bước \(4\): Nếu vẫn còn ít nhất một con LỪA chưa được sang sông, GSPVH sẽ chèo thuyền quay lại bờ xuất phát rồi thực hiện lại từ bước \(1\) để đưa các con LỪA khác lên thuyền. Quá trình này được lặp đi lặp lại cho tới khi toàn bộ đàn LỪA đều đã qua sông.

Chắc hẳn mọi người đều biết GSPVH là người thon gọn, bo đì đẹp, dáng chuẩn, nên khối lượng của GSPVH là không đáng kể. Lấy ví dụ, giả sử GSPVH có \(n = 10\) con LỪA với khối lượng lần lượt là \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\) và tải trọng của thuyền là \(c = 38\), quá trình đưa đàn LỪA sang sông của GSPVH diễn ra như sau:

• GSPVH đưa các con LỪA có khối lượng \(29, 7\) và \(2\) lên thuyền, lái qua sông rồi quay lại.
• GSPVH đưa các con LỪA có khối lượng \(23\) và \(13\) lên thuyền, lái qua sông rồi quay lại.
• GSPVH đưa các con LỪA có khối lượng \(19\) và \(17\) lên thuyền, lái qua sông rồi quay lại.
• GSPVH đưa các con LỪA có khối lượng \(11, 5\) và \(3\) lên thuyền, lái qua sông. Tới thời điểm này, toàn bộ đàn LỪA \(10\) con đều đã được đưa sang sông.

Như vậy, trong trường hợp này, GSPVH cần \(4\) lượt chèo thuyền mới có thể đưa được toàn bộ đàn LỪA qua sông.

Do thời gian có hạn, GSPVH muốn đưa toàn bộ đàn LỪA qua sông với không quá \(k\) lượt chèo thuyền. Các bạn hãy giúp GSPVH tìm ra tải trọng \(c\) nhỏ nhất của thuyền để thực hiện được điều này.

Input

• Dòng đầu tiên chứa số nguyên \(\theta\) là số bộ dữ liệu. Tiếp sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 20000)\) lần lượt là số con LỪA trong đàn LỪA của GSPVH và số lượt chèo thuyền tối đa để GSPVH đưa toàn bộ đàn LỪA sang sông.
  • Dòng thứ ba chứa \(n\) số nguyên \(w_{1}, w_{2}, \ldots, w_{n}\) \((1 \leq w_{i} \leq 3000)\) là khối lượng các con LỪA.
• Gọi \(N\) là tổng giá trị của \(n\) trong các bộ dữ liệu, dữ liệu vào đảm bảo \(N \leq 100000\).

Output

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là giới hạn khối lượng của thuyền \(c\) nhỏ nhất để GSPVH có thể đưa toàn bộ đàn LỪA qua sông trong không quá \(k\) lượt.

Scoring

• Subtask \(1\) (\(11\) điểm): \(n \leq 3\).
• Subtask \(2\) (\(16\) điểm): \(w_{i} \leq 2\).
• Subtask \(3\) (\(18\) điểm): \(n \leq 50\) và \(N \leq 250\).
• Subtask \(4\) (\(13\) điểm): \(n \leq 2000\) và \(N \leq 10000\).
• Subtask \(5\) (\(12\) điểm): Không có ràng buộc gì thêm.

Example

3
7 3
2 2 7 1 9 9 7
6 6
1 1 2 3 5 8
5 1
1 4 9 16 25

14
8
55