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 ice cream machines numbered to where each machine makes scoops of ice cream per batch. When a child makes an order of scoops, he would like to serve exactly 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 to that he can successfully serve with this strategy.
Constraints
Subtask 1 [20%]
Subtask 2 [80%]
No further constraints.
Input Specification
The first line will contain two space-separated integers, and .
The next line will contain space-separated integers, .
Output Specification
Output the number of orders from to that Lou can serve.
Sample Input
4 10
2 5 3 8
Sample Output
6
Explanation for Sample Output
Lou can make , , , , , with these sizes but not , , , .
Comments