22925번 - 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.)

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 a single integer, which is the number of possible problem sets with Nice difficulty distributions.