LCC '22 Contest 3 S2 - Serving Sizes

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Lou is a cool guy who sells ice cream by the beach in his ice cream truck. On hot summer days like today, he is looking to make a profit on the children running around.

Lou's truck has N ice cream machines numbered 1 to N where each machine makes a_i scoops of ice cream per batch. When a child makes an order of X scoops, he would like to serve exactly X scoops by combining batches from any subset of machines to make a larger one equal to their sum (he may never remove scoops from a batch). However, the machines must be cleaned after each batch so Lou may not take multiple servings from the same machine.

Lou would like you to help him find the total number of orders from 1 to M that he can successfully serve with this strategy.

Constraints

1 \le N \le 10^2

1 \le M \le 10^4

1 \le a_i \le 10^2

Subtask 1 [20%]

1 \le N \le 18

Subtask 2 [80%]

No further constraints.

Input Specification

The first line will contain two space-separated integers, N and M.

The next line will contain N space-separated integers, a_1, a_2, ..., a_N.

Output Specification

Output the number of orders from 1 to M that Lou can serve.

Sample Input

4 10
2 5 3 8

Sample Output

6

Explanation for Sample Output

Lou can make 2, 3, 5, 7, 8, 10 with these sizes but not 1, 4, 6, 9.


Comments

There are no comments at the moment.