The government of a neighboring country is running a game show called "Let's Make Some Money!". During the final round (the "Round of Eleven"), the contestant is given a number n and some money. The goal is to change the number into a multiple of 11. Contestants are allowed to spend 1 dollar to either increment a digit of n (to a maximum of 9) or decrement a digit of n (to a minimum of 0). Upon reaching a multiple of 11 that has not been selected this week, the contestant can either leave with the money that they have not spent or choose to keep going. For example, if n is 31 and the contestant has 4 dollars, he can change n to 11 (by decrementing the 3 twice), 22 (by decrementing 3 and incrementing 1) or 33 (by incrementing 1 twice). For each one, he would receive 2 dollars.
As ruler of Rainban, you have decided that you will allow each of your subjects to attend the show and collect all of their winnings; fortunately for you, you have so many subjects that you can win every prize on the show. This week, all subjects will get to start with the same values of n and money. Once one subject selects a multiple of 11, that multiple cannot be used by any future subject. In addition, you cannot add any digits to the number (so you cannot change 9 into 19), but you can create leading zeroes (for example, changing 19 into 09). Return the total amount of money that can be won, if your subjects play optimally. See the examples for clarification.
|