A given number k is to be expressed as a sum of products of integers keeping in mind that the integers used in above process do not exceed their cumulative sum as 100.
For e.g.,
k = 19 can be expressed as 15 + 4 or 3*5 + 2*2, so the cumulative sum is 3 + 5 + 2 + 2 = 12
A simple approach is to prime factorize the given integer but the problem arises when the sum of prime factors exceed 100 and in expressing primes as in required form.
k can be large upto 100000.
One method would be to use the base 3 (or ternary) representation of $k$.
For example, if the number is $k=500$, then you could notice that $3^5 = 243$, so $$500 = 3 \cdot 3\cdot 3\cdot 3\cdot 3\cdot 2 + 7\cdot 2$$
Or if $k=1000$, I would use $$1000 = 3^6 + 3^5 + 3^3 + 1 = 729 + 243 + 27 + 1$$