Review - Energy Boosters

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 C_i where C_i is the capacity of the i^th booster. There are f_i 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 x 10⁵
• 1 <= f_i <= 1000, where 1 <= i <= N
• 1 <= C_i <= 10⁵, where 1 <= i <= N

Sample Input 1

3
1
2
3
3
1
2
1
6

Sample Output 1
6

Explanation
N = 3
capacities = {1, 2, 3}
frequencies = {1, 2, 1}
K = 6

It's possible to consume capacity of 1 unit by consuming 1 bottle of capacity 1 unit
It's possible to consume capacity of 2 units by consuming 1 bottle of capacity 2 units
It's possible to consume capacity of 3 units by consuming 1 bottle each of capacity 1 unit and 2 units respectively.
It's possible to consume capacity of 4 units by consuming 2 bottles of capacity 2 units
It's possible to consume capacity of 5 units by consuming 1 bottle each of capacity 2 units and 3 units respectively
It's possible to consume capacity of 6 'units by consuming 1 bottle each of capacity 1 unit, 2 units and 3 units respectively.
Hence. CDC is 6

Sample Input 2
2
1
2
2
2
1
5

Sample Output 2
4

Explanation
N = 2
capacities = {1, 2}
frequencies = {2, 1}
K = 5

It's possible to consume capacity of 1 unit by consuming 1 bottle of capacity 1 unit
It's possible to consume capacity of 2 units by consuming 1 bottle of capacity 2 units
It's possible to consume capacity of 3 units by consuming 1 bottle each of capacity 1 unit and 2 units respectively
It's possible to consume capacity of 4 units by consuming 2 bottles of capacity 1 unit and 1 bottle of capacity 2 units
It's not possible to consume capacity of 5 units
Hence, CDC is 4.

Sample Input 3
3
12
8
10
3
1
1
1
5

Sample Output 3
0

Explanation
N = 3
capacities = {12, 8, 10}
frequencies = {1, 1, 1}
K = 5

It's not possible to consume capacity between 1 to 5 units, since each of the bottle has a capacity greater than 5. Hence, CDC is 0.

How to solve this question with the given constraints?