Next number with k fives Challenge:

Your program will take two integers n and k as input, and output the smallest integer greater than (but not equal to) n that contains at least k occurrences of the digit 5. 

You can assume 1 ≤ k ≤ 15 and 1 ≤ n &lt; 10**15.

This is a restricted-time challenge. Your program must run on TIO for all of the test cases and complete within 10 seconds in total.

General rules:


This is code-golf, so the shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for any programming language.
Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call. The function parameters may be taken in either order, but please specify in your answer. 
Default Loopholes are forbidden.
You must add a link with a test for your code (i.e. TIO).
The answer header should list the score in bytes but also the total time taken for all test cases on TIO
If your language is not on TIO, the code should finish far under 10 seconds on your machine so that you're confident it's fast enough on any reasonable computer.
Adding an explanation for your answer is highly recommended.


Test Cases:

(n, k) -&gt;  output
(53, 2) -&gt; 55
(55, 1) -&gt; 56
(65, 1) -&gt; 75
(99, 1) -&gt; 105
(555, 3) -&gt; 1555
(557, 1) -&gt; 558
(5559, 3) -&gt; 5565
(6339757858743, 5) -&gt; 6339757859555
(99999999999999, 15) -&gt; 555555555555555


Program Example:

This program is correct.
R, 85 84 76 74 bytes, 0.250s on TIO

f=function(n,k,m=nchar(gsub(&quot;[^5]&quot;,&quot;&quot;,n+1))-k)`if`(m&lt;0,f(n+.1^m/50,k),n+1)

Try it online!
-1 byte thanks to Robert S.
-8 bytes thanks to Giuseppe.
The nchar(gsub(...)) part counts the number of 5s.
A simple recursive solution would be to increment by 1 until the answer is found, but this would not meet the time restriction. To meet the time restriction, this function makes use of the fact that if there are p missing 5s, we can increment by 2*10^(p-2) (represented as the golfier .1^m/50, with m=-p).
Note that when p=1, the increment becomes 0.2. This is OK, since after 5 steps we come back to an integer, and none of the decimal numbers encountered in the mean time have an extra 5. If instead we were to increment by 5*10^(p-2) or by 1*10^(p-2), then we would find f(24, 1)=24.5 instead of 25 for example.