We are given a set of $ n $ coins with denominations $ v_1, v_2, ldots, $ v_n and a number $ x $.

The rooms must be divided into persons, provided that each person's rooms total at least $ x $.

For example, if $ x = $ 1, $ n = $ 2, and $ v_1 = v_2 = $ 2then there are two possible distributions: one where the person 1 receives the coin # 1 and the person 2 gets the coin # 2, and one with the reverse. (These distributions are considered separate even if both parts have the same denomination.)

I am interested in counting the possible distributions. I'm sure this can be done in $ O (nx) $ time and $ O (n + x) $ space using dynamic programming; but I do not see how.