numericalstrings

Problem Description

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?

Input

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.

Output

The output should contain exactly one number, the largest possible numerical string formed by concatenating K of these numerical strings together.

Limits

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.

Sample Input

5 3
5
541
33
9
98

Sample Output

9854133

Submitting to 'numericalstrings'


You're not logged in! Click here to login


Submitting to 'numericalstrings'


You're not logged in! Click here to login


Submitting .cpp to 'numericalstrings'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 128MB
Your best score: 0
Source: RI November Course Stage 2 Selection Test 2019
Editorial: 1

Subtask Score
1 12
2 17
3 11
4 22
5 38
6 0