Problem B
Contest Construction
The ICPC NAC staff have written a number of problems and wish to construct a problem set out of them. Each problem has a positive difficulty rating.
A contest has a Nice difficulty distribution if, when the difficulties of the problems are sorted in ascending order, every problem after the second has a difficulty rating less than or equal to the sum of the difficulty ratings of the two problems immediately preceding that problem.
Given the difficulty ratings of a set of problems and the number of problems desired for the set, count the number of problem sets with Nice difficulty distributions. Two problem sets are distinct if and only if there is some problem in one problem set but not in the other. (Specifically, note that two problem sets are the same even if the problems are permuted.)
Input
The first line of input contains two integers
Each of the next
Output
Output a single integer, which is the number of possible problem sets with Nice difficulty distributions.
Sample Input 1 | Sample Output 1 |
---|---|
5 4 2 1 4 3 5 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
8 5 1 2 3 5 8 13 21 34 |
4 |