Sam has recently started his own company known as Codage etoile. He cares a lot about his employees. Due to high work load, he buys some special types of energy boosters for his employees. There are N different types of energy boosters. Each energy booster provides the capacity Ci where Ci is the capacity of the ith booster. There are fi bottles of ith booster.

A person gets the cumulative capacity of all the boosters consumed. That is, if a person drinks 2 bottles, one of an energy booster with capacity 2 units and another of an energy booster with capacity 3 units, it will give him/her a cumulative capacity of 5 units. Sam wants to find the count of distinct capacities, between 1 to K (inclusive), which can be achieved on drinking these boosters. For sake of convenience, count of distinct capacities is labelled as 'CDC'.

Constraints:

$$$1 <= N <= 100$$$

$$$1 <= K <= 15*1e5$$$

$$$1 <= fi <= 1000,$$$ $$$where$$$ $$$1 <= i <= N$$$

$$$1 <= Ci <= 1e5,$$$ $$$where$$$ $$$1 <= i <= N$$$

Sample Input 1:

3 1 2 3 3 1 2 1 6

Sample Output 1: 6

I am not able to solve this problem, can someone please help.

Source: https://leetcode.com/discuss/interview-question/1929527/De-Shaw-India-or-OA