Counting K-gons

Time limit2sMemory limit128 MB

Summary

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.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Sorting, Math
Solved: No attempts yet

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.

Examples5

Example 1
Input
```
6
4 4 4 2 2 2
3
```
Expected output
```
11
```
Example 2
Input
```
4
1 1 1 1
3
```
Expected output
```
4
```
Example 3
Input
```
4
2 3 4 5
3
```
Expected output
```
3
```
Example 4
Input
```
5
10 1 4 9 20
4
```
Expected output
```
2
```

Example 5

Input

13
3310 1660 211 1260 160 213 884 539 17212 2025 105 120 5510
7

Expected output