Before revision:  We prove that this problem cannot be solved in  O((N \cdot t_{max})^{1-\epsilon}) time , for t_{max}=\max_i t_i and any \epsilon > 0, assuming the \forall \exists Strong Exponential Time Hypothesis (\forall \exists-SETH).
After revision:  We prove that this problem cannot be solved in O((N \cdot t_{max})^{1-\epsilon}) , for t_{max}=\max_i t_i and any \epsilon > 0, assuming the \forall \exists Strong Exponential Time Hypothesis (\forall \exists-SETH).