/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 550 点
問題文
数字のみからなる N 個の文字列 S_1,\ldots,S_N が与えられます。
これらからちょうど K 個を選んで好きな順序で連結した文字列を、(先頭の余分なゼロを除いて)十進表記の整数として解釈したときの値として考えられる最大値を求めてください。
なお、全ての文字が 0 である文字列を、先頭の余分なゼロを除いて十進表記の整数として解釈したときの値は 0 であるとします。
制約
- 1 \leq K \leq N \leq 10^5
- S_i は数字のみからなる長さ 1 以上 10 以下の文字列
- N,K は整数である
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 2 123 45 6
出力例 1
45123
123, 45, 6 から 2 個選んで連結してできる文字列は 12345, 1236, 45123, 456, 6123, 645 の 6 種類あります。
これを十進表記の整数と解釈したときの最大値は 45123 です。
入力例 2
5 3 00000 00 1 0000 000
出力例 2
1000000000
入力例 3
9 9 0000000001 000000002 00000003 0000004 000005 00006 0007 008 09
出力例 3
90080007000060000050000004000000030000000020000000001
答えは先頭の余分なゼロなしで出力する必要があります。
Score : 550 points
Problem Statement
You are given N strings S_1,\ldots,S_N consisting of digits.
Find the maximum possible value, when interpreted as a decimal integer (after removing extra leading zeros), of a string obtained by choosing exactly K of these strings and concatenating them in any order of your choice.
Here, the value obtained by interpreting a string consisting entirely of the character 0 as a decimal integer after removing extra leading zeros is defined to be 0.
Constraints
- 1 \leq K \leq N \leq 10^5
- S_i is a string of length between 1 and 10 (inclusive) consisting of digits.
- N and K are integers.
Input
The input is given from Standard Input in the following format:
N K S_1 \vdots S_N
Output
Output the answer.
Sample Input 1
3 2 123 45 6
Sample Output 1
45123
There are six strings obtained by choosing two of 123, 45, 6 and concatenating them: 12345, 1236, 45123, 456, 6123, 645.
Among these, the maximum value when interpreted as a decimal integer is 45123.
Sample Input 2
5 3 00000 00 1 0000 000
Sample Output 2
1000000000
Sample Input 3
9 9 0000000001 000000002 00000003 0000004 000005 00006 0007 008 09
Sample Output 3
90080007000060000050000004000000030000000020000000001
The answer must be output without extra leading zeros.