Win the Bonus

Time Limit: 10 Seconds Memory Limit: 32768 KB

There is a game with m bankers, each holding a string of integers of length 3 (note: an integer that has less than 3 digits has zeros filled to the left, e.g. 5 is considered as 005). Each banker assigns to his\her string some bonus or penalty points. As a player, you are supposed to select n digits from the set {0,1,2,3,4,5,6,7,8,9} to form your own integer string. If your string contains some of the bankers' strings, then you will gain or lose points accordingly. For example, if there are two bankers assigning 20 bonus points to 356 and 10 penalty points to 674 respectively, and your string is 035674, then since 356 and 674 both appear once in your string, the score you get will be 20-10=10. The player getting the most points wins the game. If there are more than one player getting the most points, the one with the smallest string number wins.
Now, suppose that Harry Potter gets to know all the bankers' secret strings and their assigned points by waving his magic wand, it is still not an easy task to win the game even with Hermione on his side. So he has come to you for help -- given the string length n, you may write a program to find the winning string.

Input

The input consists of several test cases.
The first line of each test case contains two integers m and n (1<=n<=10000), where m is the number of bankers and n is the required length of the player's string.
The following m lines contain m pairs of integers which are the banker's string and the points assigned to it.
You may assume that all the bankers' strings are distinct.

Output

For each test case you are supposed to output the winning string you find in a line. No extra spaces are allowed.

Sample Input

2 5
356 20
674 -10

Sample Output

Submit

Source: Zhejiang University Local Contest 2002, Preliminary