God of Numbers

Time limit2sMemory limit128 MB

Summary

Choose N numbers from K given natural numbers, using every distinct input at least once, and arrange them to concatenate into the largest possible number.

Level: Medium6 of 10
Topics: Greedy, Sorting, String
Solved: No attempts yet

Problem

O Sejun, the god of natural numbers, has K natural numbers. He wants to choose exactly N numbers from them and concatenate the chosen numbers in any order to make the largest possible number.

A number may be used more than once, but each of the K input numbers must be used at least once. If the same value appears multiple times in the input, each occurrence must be used at least once.

Print the largest number that can be made while satisfying these conditions.

Input

The first line contains K and N separated by a space. K and N are natural numbers no greater than 50, and N is at least K.

Each of the next K lines contains one natural number. Each number is no greater than 1,000,000,000. The same number may appear more than once; in that case, it must be used at least as many times as it appears in the input.

Output

Print the largest number that can be made by choosing and concatenating N numbers under the given conditions.

Examples5

Example 1
Input
```
3 3
3
2
7
```
Expected output
```
732
```
Example 2
Input
```
2 4
4
7
```
Expected output
```
7774
```
Example 3
Input
```
3 4
1
10
100
```
Expected output
```
110100100
```
Example 4
Input
```
4 9
4
4
4
4
```
Expected output
```
444444444
```
Example 5
Input
```
3 3
1
1
2
```
Expected output
```
211
```