Có N thẻ, thẻ i ghi chuỗi chữ thường Si. Hãy chọn đúng K thẻ và nối các chuỗi trên chúng theo một thứ tự tùy ý để thu được chuỗi nhỏ nhất theo thứ tự từ điển.
Input
Dòng đầu chứa N và K.
N dòng tiếp theo chứa các chuỗi ghi trên thẻ.
Output
In chuỗi nhỏ nhất có thể nhận được sau khi chọn và sắp đúng K thẻ.
Constraints
1≤K≤N≤50.
1≤∣Si∣≤50; mỗi Si chỉ gồm chữ thường.
Scoring
Subtask 1 (50% số điểm): N≤10.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
4 3
b
a
baa
ba
Output
abaab
Giải thích: Trong các cách chọn ba thẻ, chuỗi abaab từ các thẻ a, baa, b nhỏ hơn mọi kết quả còn lại.
Lời giải tóm tắt
Phân tích: Sắp các thẻ theo comparator a+b < b+a. Tính chất đổi chỗ cho biết trong một nghiệm tối ưu, các thẻ được chọn có thể xuất hiện theo thứ tự này. Sau khi sắp, bài còn lại là chọn một subsequence đúng K phần tử.
Phân tích: Đặt dp[j] là chuỗi nhỏ nhất tạo được sau khi đã duyệt một số thẻ và chọn đúng j thẻ. Khởi tạo dp[0] là chuỗi rỗng, các trạng thái khác chưa hợp lệ.
Phân tích: Duyệt từng thẻ card; cập nhật j giảm dần để mỗi thẻ dùng tối đa một lần: dp[j+1] = min_lex(dp[j+1], dp[j] + card). Kết quả là dp[K].
Tính đúng đắn: Nếu trong một cách ghép có hai thẻ kề nhau a,b nhưng b+a < a+b, đổi chỗ chúng làm toàn chuỗi nhỏ hơn và không ảnh hưởng phần trước/sau. Lặp phép đổi chỗ cho thấy tồn tại nghiệm tối ưu có thứ tự theo comparator đã sắp.
Tính đúng đắn: Sau khi thứ tự cố định, mọi tập K thẻ tương ứng duy nhất với một subsequence. Quy nạp theo số thẻ đã duyệt chứng minh dp[j] là chuỗi nhỏ nhất của mọi subsequence j thẻ: mỗi nghiệm hoặc bỏ thẻ mới, hoặc lấy nó sau một nghiệm j−1 tối ưu. Vì chuyển xét đủ hai trường hợp và lấy min từ điển, dp[K] đúng.
Độ phức tạp: O(NK·L) thao tác ký tự ở mức khái niệm, với L là độ dài chuỗi kết quả; O(K·L) bộ nhớ.