Consider the following algorithm (a variant of Levin's algorithm):
Run the first $n$ algorithms in parallel. Additionally, run in parallel a brute-force algorithm that tries all possible solutions one by one. (Run all algorithms with the same speed.)
Stop when one of the algorithms finds a solution.
Consider two cases (given an input $x$ of length $n$):
$Q$ is one of the first $n$ algorithms. Then the running time is $O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$.
$Q$ is not one of the first $n$ algorithms (thus $n < 2^{|Q|}$). Then the running time is bounded by the running time of the brute-force algorithm. We have that the running time is $2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$.
We have $$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n) + 2^{2^{O(|Q|)}}.$$
(Here, $f(n)$ is polynomial and $g(n)$ is double exponential in $n$; we can improve the dependance of $g(n)$ on $n$ by worsening the dependence of $f(n)$ on $n$.)