# Problem AP

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 $n$ ($3 \le n \le 50$) and $k$ ($3 \le k \le 18, k \le n$), where $n$ is the number of problems the judges have written, and $k$ is the number of problems they wish to put in the problem set.

Each of the next $n$ lines contains a single integer $d$ ($1 \le d \le 10^9$). These are the problem difficulties.

## 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 |