cho.sh

Counting K-gons

Count the subsets of exactly K segments (from N, N up to 50) whose longest side is shorter than the sum of the rest, forming a valid K-gon.

Medium7Dynamic programmingCombinatoricsSortingMathNo attempts yetTime limit2sMemory limit128 MB

Problem

There are N line segments numbered from 1 to N, and the length of each segment is given. Choose exactly K of these segments and use them as the sides of a K-gon. Each segment may be used at most once.

Two choices are considered different if there is a segment number used in one choice that is not used in the other. Segments with the same length are still different when their numbers are different.

A chosen set of K segments can form a K-gon when the longest chosen segment is shorter than the sum of the other K-1 chosen segments. Count how many different choices can form a K-gon.

Input

The first line contains N. N is a positive integer not greater than 50.

The second line contains the lengths of the N segments. Each length is a positive integer not greater than 50,000.

The third line contains K. K is a positive integer with 3 <= K <= 10.

Output

Print the answer on the first line.