Party Medley

Interview

Time limit1sMemory limit2048 MB

Summary

Count the teams of three distinct students whose max minus min rating is at most M, and find the largest rating sum among those teams.

Level: Medium4 of 10
Topics: Brute force, Sorting, Combinatorics
Solved: No attempts yet

Problem

ICPC University has $N$ students, numbered from $1$ to $N$ , in its Competitive Programming club. Student $i$ has a rating of $A_i$ , which estimates their skill in competitive problem-solving.

Contest season is coming, and Morgan, the coach of the club, wants to send at most one good team to a particular contest because the budget is limited. A team consists of exactly $3$ different students. If a team consists of students $i$ , $j$ , and $k$ , then their team rating is $A_i + A_j + A_k$ , and their rating difference is $\max(A_i, A_j, A_k) - \min(A_i, A_j, A_k)$ .

Morgan considers a team balanced if its rating difference is at most a threshold $M$ . Among balanced teams, Morgan wants the team rating to be as large as possible.

Morgan asks for two values. The first is the number of balanced teams that can be formed. The second is the largest team rating of a balanced team that can be formed. Two team configurations are different if at least one student differs between them.

Input

The first line contains two integers $N$ and $M$ ( $3 \le N \le 200$ ; $0 \le M \le 4000$ ). The next line contains $N$ integers $A_i$ ( $0 \le A_i \le 4000$ ), the rating of student $i$ .

Output

If at least one balanced team configuration exists, print two space-separated integers on one line: the number of balanced team configurations, and the largest team rating of any balanced team. If no balanced team configuration exists, print -1 on one line.

Examples4

Example 1
Input
```
5 150
1400 1425 1250 4000 1300
```
Expected output
```
2 4125
```
Example 2
Input
```
4 100
2000 1900 1800 2100
```
Expected output
```
-1
```

Example 3

Input

8 4000
100 200 300 400 500 600 700 800

Expected output

56 2100

Example 4
Input
```
8 0
10 10 10 20 20 20 30 30
```
Expected output
```
2 60
```