The input to the problem consists of (i) an array $A[1,2, \ldots, n]$ of $n$ positive integers and (ii) a positive integer $T$. We are given the guarantee that at least one element of the array is less than or equal to $T$. The task is to find the maximum sum of a non-empty sub-collection of the integers from $A$ which is less than or equal to $T$.
Describe an algorithm that solves this problem in $O(n T)$ time. The algorithm should take an array $A[1,2, \ldots, n]$ and an integer $T$ as described above, and should output a number $T^{\prime} \leq T$ that is closest to $T$ and can be realized as the sum of some subcollection of $A$. It is not required that the algorithm find the subset of indices which forms the sum $T^{\prime}$.
