Smallest Number with Fives

Time limit1sMemory limit128 MB

Summary
Find the smallest integer greater than N that contains the digit 5 at least K times in its decimal form.
Level

Medium6 of 10

Topics
Math, Greedy, Brute force
Solved
No attempts yet

Problem

Given natural numbers N and K, find the smallest natural number greater than N whose decimal representation contains the digit 5 at least K times.

Input

The first line contains two natural numbers N and K separated by a space.

  • 1 <= N <= 10^15
  • 1 <= K <= 15

Output

Print the smallest natural number greater than N whose decimal representation contains the digit 5 at least K times.

Examples3

  1. Example 1

    Input
    99 1
    Expected output
    105

  2. Example 2

    Input
    595 2
    Expected output
    655

  3. Example 3

    Input
    123456789012345 3
    Expected output
    123456789012355