Peanut has N numerical strings, each of them containing only digits '1' to '9' and at most 5 characters long. He wishes to select K of these strings, and join them together in a certain order, to form the largest possible resultant number. What is the largest number he can form?
The first line of input will contain two integers, N and K.
The next N lines of input will contain a single numerical string each.
The output should contain exactly one number, the largest possible numerical string formed by concatenating K of these numerical strings together.
For all subtasks: 1 ≤ K ≤ N ≤ 100 000.
Subtask 1 (12%): All numerical strings are 1 character long.
Subtask 2 (17%): All numerical strings are of the same length.
Subtask 3 (11%): K = 1.
Subtask 4 (22%): K = N.
Subtask 5 (38%): No additional constraints.
5 3 5 541 33 9 98
9854133
Subtask | Score |
---|---|
1 | 12 |
2 | 17 |
3 | 11 |
4 | 22 |
5 | 38 |
6 | 0 |