The technology behind the fridge has changed little over the years. Even so, many of the original owners of the Fred W. Wolf domestic refrigerator of 1913 would be amazed by the size and features of the modern appliances. However, since the 1960s one thing has been common for all fridge owners around the world: fridge magnets.

An effective, albeit lazy, way to keep a small child entertained is to supply them with a set of magnetic numbers and a large magnetic surface, such as said fridge, to provide the playing field upon which to apply these digits.

Far from a time-wasting exercise, this provides valuable training in the mathematical field of counting: moving the digits around to form “1”, “2”, and so on up to such heights as “10”, “11”, “12”, and even beyond.

The possibilities are endless! ...Or at least, they would be, if the supply of digits was not limited. Given the full list of what numbers we are in possession of, what is the smallest positive number that cannot be made using each of digits at most once?

-----Input-----
 - One string of at most $1000$ digits, containing the available digits in no particular order.

-----Output-----
 - One line containing one positive integer: the smallest natural number that it is not possible to assemble from the supplied digits.

-----Examples-----
Sample Input 1:
7129045863
Sample Output 1:
11

Sample Input 2:
55
Sample Output 2:
1

Source: kattis | Difficulty: MEDIUM
Tags: Greedy algorithms


Solutions: